13 ***Planar graphs***13 ***Planar graphs***13.2 Coloring of Planar graphs

13.1 Euler’s formula and Kuratowski’s theorem

Theorem 13.5 (Euler’s formula).

Let $G$ be a plane graph with $v$ vertices, $e$ edges and $f$ faces. Then $v-e+f=1+\beta_{0}(G)$ where recall that $\beta_{0}(G)$ is the number of connected components.

Proof.

The proof proceeds by showing the formula for forests and then inductively verifying it for connected graphs. For forest, observe that there is only one face because of the definition of the length of a face, that every edge is a cut-edge, $v-e=\beta_{0}(G)$ and Exercise 13.4.

If the formula holds for trees, then one can show that if $G, H$ are two disjoint plane graphs then there exists $u\in G,v\in H$ such that $G^{\prime}=G\cup H\cup(u,v)$ is also a plane graph with the number of faces being $f^{\prime}(G)=f(G)+f(H)-1$ . ∎

Lemma 13.6.

Suppose $G$ is a connected plane graph with $v\geq 3$ . Then $e\leq 3v-6.$ Further if $G$ has no triangles then $e\leq 2v-4.$

Proof.

Note that if $\partial F$ corresponds to a cycle, $l(F)\geq 3$ and if not $l(F)\geq 4$ as $v\geq 3$ and $G$ is connected. Thus, we have by Euler’s formula that

3(2-v+e)=3f\leq\sum_{F}l(F)=2e

and so $e\leq 3v-6$ . Now, if $G$ has no triangles, then $l(F)\geq 4$ for all $F$ and the above inequality yields that $e\leq 2v-4$ . ∎

Using the above lemma, we can show that $K_{3,3}$ and $K_{5}$ are not planar. A direct constructive proof using some geometric arguments are also possible for non-planarity of $K_{3,3}$ and $K_{5}$ .

We say $H$ is a minor of a graph $G$ if $H$ is obtained from $G$ by a sequence of the following operations : (i) Edge-deletion. (ii) Vertex-deletion or (iii) edge-contraction. The three operations preserve planarity (see Section 13.4.

Now, we shall state without proof one of the important theorems - Kuratowski’s theorem . We shall rather state an equivalent form of the same known as Wagner’s theorem.

Theorem 13.7 (Wagner’s theorem; ).

A graph if planar iff it has no $K_{3,3}$ or $K_{5}$ minor.

A graph is a triangulation if it is connected and $l(F)=3$ for every face $F$ . A planar graph is said to be maximal if addition of any edge makes it non-planar.

Lemma 13.8.

$G$ is a plane graph with $v\geq 3$ . TFAE

1.

$e=3v-6$ and $G$ is connected
2.

$G$ is a triangulation.
3.

$G$ is a maximal planar graph.

Proof.

The equivalence of (i) and (ii) is by noting that the inequality in the proof of Lemma 13.6 is an equality in this case. ∎

Exercise 13.9.

Show that (ii) and (iii) equivalent in the above lemma.