Plane Graphs, Euler's Formula and the Five Colour Theorem — Examples

By [L2], a tree on $n$ vertices has $n-1$ edges, and its plane embedding has one face by Every plane forest has exactly one face. Thus $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }=n-(n-1)+1=2$. This includes the one-vertex tree, for which the edge count is zero.

A plane cycle $C_n$, in the notation of Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices, has $n$ vertices and $n$ edges. Its polygon bounds one face and has the unbounded face on the other side, so $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }=n-n+2=2$.

Embed three vertices of $K_4$ as a triangle and place the fourth inside it, joined to all three corners. The graph has four vertices, six edges, three bounded triangular faces, and the unbounded triangular face. Hence $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }=4-6+4=2$, as [L1] requires.

Draw three vertices as a triangle, place the fourth inside it, and join that vertex to the three corners. The six edges meet only at their common endpoints, so this is a plane embedding of $K_4$.

By [F1] and [F2], the four vertices must receive pairwise distinct colours in any proper colouring. Assigning a different colour to each vertex is proper, so $\chi (K_4)=4$. Thus a planar graph need not be three-colourable, although Five colour theorem: every planar graph has chromatic number at most five supplies five colours for every planar graph.

Delete the vertex $12$. Take the branch classes $A=\{13,14,15\}$ and $B=\{23,24,25\}$. The six direct branch connections are $13$ to $24,25$, $14$ to $23,25$, and $15$ to $23,24$. The remaining three are the paths $13-45-23$, $14-35-24$, and $15-34-25$.

Every consecutive pair in the displayed list has disjoint labels, so it is an edge by [F1]. The internal vertices $45,35,34$ are distinct and are not branch vertices; all other listed connections are single edges. Thus the nine paths are internally disjoint and form a subdivision, in the sense of Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors, of $K_{3,3}$ with branch classes $A$ and $B$. This subdivision lies in a subgraph of the Petersen graph, so [L1] proves that the Petersen graph is nonplanar.

Embed the three $s$-$t$ paths in cyclic order. Write $f_{12},f_{23},f_{31}$ for the faces between the indicated path pairs. In the dual of The plane dual multigraph, with a vertex for each face and one crossing edge for each primal edge, the path lengths $1,2,3$ give respectively that many parallel dual edges between the two faces on each side of the path. Before accounting for $sw$, the degrees of $f_{12},f_{23},f_{31}$ are $3,5,4$. The bridge may be drawn into any one of these face sectors at $s$; it then gives a dual loop at that face.

In one embedding draw $sw$ into $f_{12}$; the dual degree multiset is then $\{5,5,4\}$. In another draw it into $f_{31}$; the dual degree multiset is $\{3,5,6\}$. These multisets differ, since a loop contributes two to its incident degree. By [F1] the two dual multigraphs are nonisomorphic, although both arise from the same connected planar graph $G$.

Before $v$ is inserted, its five prospective neighbours use all five colours. In the subgraph induced by colours $1$ and $3$, both $v_1$ and $v_3$ are isolated: their two cycle neighbours have colours $2,5$ and $2,4$, respectively. In particular there is no alternating $1$-$3$ path between them, consistently with [L2].

Swap colours $1$ and $3$ on the Kempe component $\{v_1\}$. The colouring remains proper by [L1]; now both $v_1$ and $v_3$ have colour $3$, but they are nonadjacent, and no rim vertex has colour $1$. Give the inserted centre $v$ colour $1$. Every spoke then has differently coloured endpoints, producing an explicit five-colouring of the plane wheel and illustrating the swap used in Five colour theorem: every planar graph has chromatic number at most five.

The two parts of $K_{3,3}$ contain three vertices each, so $\mathrm{\mid }V\mathrm{\mid }=6$. Every vertex in either part is adjacent to all three vertices of the other part, giving $\mathrm{\mid }E\mathrm{\mid }=3\cdot 3=9$; equivalently this follows from Handshake lemma: the sum of the vertex degrees is twice the number of edges. Consequently $9\le 3\cdot 6-6=12$, so the necessary inequality in [L1] holds.

Nevertheless [L2] says that this graph is nonplanar. Hence satisfying the planar simple-graph edge bound does not suffice for planarity.

The first coordinate of $\gamma (t)$ is $t$, so $\gamma$ is injective. For $t>0$ it is continuous, and $\mathrm{\mid }t\sin (1\mathrm{/}t)\mathrm{\mid }\le t$ shows continuity at $0$. Thus [F1] makes it a continuous arc with distinct endpoints. It is not polygonal: the second coordinate vanishes at infinitely many points $t=1\mathrm{/}(k\pi )$ accumulating at $0$ and changes sign between them, whereas a finite union of line segments either has only finitely many such crossings of the horizontal axis or contains a nontrivial segment of that axis. The latter is impossible here because $t\sin (1\mathrm{/}t)$ is not identically zero on any interval.

Use the image of $\gamma$ as the drawing of the sole edge of a two-vertex abstract graph. The drawing is injective but its edge is not a polygonal arc in the sense of Polygonal arcs and polygons as non-self-intersecting finite unions of line segments in ${\mathbb{R}}^2$, so [L1] excludes this particular drawing from the page's class of plane graphs. This does not make the abstract one-edge graph nonplanar: drawing its edge as a straight segment gives a plane embedding.