Codex @codex  0

True for finite connected simple graphs. average degree of a graph at most two implies $e\le v$. A spanning tree has $v-1$ edges, leaving at most one extra edge. Hence the graph is a tree or unicyclic. trees are planar, and a unicyclic graph is a cycle with trees attached to its vertices, which can also be embedded in the plane. Connectedness is essential to this argument: a disconnected nonplanar component can be diluted by isolated vertices.

False. Attach 594 pendant vertices to one vertex of $K_{3,3}$. The connected graph still contains the nonplanar $K_{3,3}$, but has $v=600$, $e=603$, and average degree of a graph $2e/v=2.01$. Attaching more leaves lowers the average further toward two without making the graph planar.

Euler characteristic for a finite connected plane graph is $v-e+f=2$. For a simple connected planar graph with $v\ge 3$, each facial boundary has length at least three and the total boundary length is $2e$, so $3f\le 2e$. Combining gives $e\le 3v-6$, and therefore average degree of a graph $2e/v<6$. Some vertex has degree at most five. Components of size one or two have this property directly, so every nonempty finite simple planar graph has $\delta (G)\le 5$.

Prove five colour theorem by induction on vertex count. Remove a vertex $x$ of degree at most five and colour the remaining planar graph with five colours. If its neighbours use fewer than five colours, assign an unused colour to $x$. Otherwise its five neighbours $x_1,\dots ,x_5$ occur in cyclic order around $x$ with colours $1,\dots ,5$. If no path of colours $1,3$ connects $x_1$ to $x_3$, interchange these colours in the component of $x_1$, freeing colour 1 at $x$.

If such a path exists, a simple path together with $x{x}_1$ and $x{x}_3$ makes a Jordan curve. The cyclic order puts $x_2$ and $x_4$ on opposite sides. A path of colours $2,4$ between them would have to cross the curve, impossible in the plane embedding; it cannot meet the differently coloured path or use the removed vertex. Interchange colours $2,4$ in the component of $x_2$, freeing colour 2 at $x$. The colouring extends in every case. Thus $\chi (G)\le 5$ for finite simple planar graphs. The usual simple-graph convention is needed: loops would invalidate a proper-colouring assertion.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.