Combinatorics

15.1.16.1 Proof. Let \(\displaystyle G\) be a graph with a nonplanar subgraph \(\displaystyle H\text{.}\) Suppose (towards a contradiction) that \(\displaystyle G\) is planar. Find a planar embedding of \(\displaystyle G\text{,}\) and delete vertices and/or edges (as appropriate) to reach the subgraph \(\displaystyle H\text{.}\) No edges that do not share an endvertex have points in common in the embedding of \(\displaystyle G\text{,}\) and edges that do share an endvertex have no other points in common. This property is not changed by deleting vertices and/or edges, so our result is a planar embedding of \(\displaystyle H\text{.}\) But this is impossible, since \(\displaystyle H\) is nonplanar. The contradiction shows that \(\displaystyle G\) must be planar.

Since \(\displaystyle K_5\) is a subgraph of \(\displaystyle K_n\) for every \(\displaystyle n \ge 6\) and \(\displaystyle K_5\) is nonplanar by Theorem 15.1.3, this shows that \(\displaystyle K_n\) is nonplanar for every \(\displaystyle n \ge 6\text{.}\) ◾

15.1.16.3 We show a planar embedding of the graph, the planar embedding with the dual graph shown in grey, and the dual graph.

15.2.10.1 We will prove that for any planar embedding of a disconnected planar graph with exactly two connected components, \(\displaystyle |V|-|E|+|F|=3\text{.}\)

Proof. We will prove this formula by induction on the number of faces of the embedding. Let \(\displaystyle G\) be a planar embedding of a graph with exactly two connected components.

Base case: If \(\displaystyle |F|=1\) then \(\displaystyle G\) cannot have any cycles (otherwise the interior and exterior of the cycle would be \(\displaystyle 2\) distinct faces). So \(\displaystyle G\) must consist of two connected graphs that have no cycles, i.e., two trees, \(\displaystyle T_1\) and \(\displaystyle T_2\text{.}\) By Theorem 12.4.5 we know that we must have \(\displaystyle |E(T_1)|=|V(T_1)|-1\) and \(\displaystyle E(T_2)=V(T_2)-1\text{,}\) so

Inductive step: We begin by stating our inductive hypothesis. Let \(\displaystyle k \ge 1\) be arbitrary, and assume that for any planar embedding of a graph that has exactly two connected components, such that the embedding has \(\displaystyle k\) faces, \(\displaystyle |V|-|E|+|F|=3\text{.}\)

Let \(\displaystyle G\) be a planar embedding of a graph that has exactly two connected components, such that the component has \(\displaystyle k+1\ge 2\) faces. Since forests have only one face, \(\displaystyle G\) must have a cycle in at least one of its components. Choose any edge \(\displaystyle e\) that is in a cycle of \(\displaystyle G\text{,}\) and let \(\displaystyle H=G\setminus\{e\}\text{.}\) Clearly, we have

and \(\displaystyle |V(H)|=|V(G)|\text{.}\) Also,

since the edge \(\displaystyle e\) being part of a cycle must separate two faces of \(\displaystyle G\text{,}\) which are united into one face of \(\displaystyle H\text{.}\) Furthermore, since \(\displaystyle e\) was in a cycle and \(\displaystyle G\) has two connected components, by an argument similar to that given in Proposition 12.3.9 \(\displaystyle H\) has two connected components, and \(\displaystyle H\) has a planar embedding induced by the planar embedding of \(\displaystyle G\text{.}\) Therefore our inductive hypothesis applies to \(\displaystyle H\text{,}\) so

This completes the inductive step.

By the Principle of Mathematical Induction, \(\displaystyle |V|-|E|+|F|=3\) for any planar embedding of graph that has exactly two connected components. ◾

15.2.10.4 The value for \(\displaystyle |V|-|E|+|F|\) on a torus is \(\displaystyle 0\text{.}\) For example, consider the graph on \(\displaystyle 5\) vertices consisting of two cycles of length \(\displaystyle 3\) that meet at a vertex. Draw this graph on a torus so that one cycle goes through the hole in the middle, and one cycle goes around the outside edge of the torus. This embedding has one face, since the first cycle cuts the torus into something resembling a cylinder, and the second cuts the cylinder into a rectangle. There are \(\displaystyle 5\) vertices and \(\displaystyle 6\) edges, so \(\displaystyle |V|-|E|+|F|=5-6+1=0\text{,}\) as claimed.

15.3.8.1 First, notice that since \(\displaystyle G\) is cubic, every vertex has valency \(\displaystyle 3\text{,}\) which is odd. Therefore, by Corollary 11.3.12, \(\displaystyle G\) must have an even number of vertices.

This means that the number of vertices in the Hamilton cycle, and the number of edges in the Hamilton cycle (which are equal) are both even. Thus, we can colour the edges of the Hamilton cycle with \(\displaystyle 2\) colours, say blue and red, alternating between the two colours all the way around the cycle.

Since the graph is cubic, each vertex is now incident to exactly one edge that has not yet been coloured. Therefore, we can colour all of the remaining edges with a single colour — green, say. Thus, we have properly \(\displaystyle 3\)-edge-coloured \(\displaystyle G\text{.}\) Since \(\displaystyle \Delta(G)=3\text{,}\) this means that \(\displaystyle G\) is a class one graph.

15.3.8.2 We use the letters \(\displaystyle R\text{,}\) \(\displaystyle G\text{,}\) \(\displaystyle B\text{,}\) and \(\displaystyle Y\) to represent the four colours. The exterior face (which appears grey in the picture) will be assigned the colour \(\displaystyle B\text{.}\)