Problem 4 - Graphs

1.

Let $G$ be a simple, connected planar graph with $n$ vertices, $e$ edges and $f$ faces. Show that there exists a vertex of degree at most 5 in $G$ by using the Euler formula concerning $n$, $e$ and $f$.

2.

Show that the vertices of $G$ can be colored by 6 colors so that adjacent vertices have different colors.

Since $G$ is a simple graph, each face is bounded by at least three distinct edges. Consider the bipartite graph formed by the set $A$ of vertices representing the faces of $G$ and the set $B$ of vertices representing the edges of $G$. Place an arc from $a\in A$ to $b\in B$ each time face $a$ is incident to edge $b$. (This graph is called the face-edge incidence graph. Clearly, the number of arcs is $\leq 2 m$ (each edge belongs to two faces) and $\geq 3f$ (each surface is composed of a least three edges). Thus:

$$f \leq \frac{2m}{3}.$$

If each vertex is the endpoint of at least 6 edges, then $n \leq \frac{2m}{6}$ (for each edge we have two distinct vertices and for each vertices at least 6 neighbours) (vertex-edge incidence graph). Form Euler's formula:

$$2 = n - m + f \leq \frac{m}{3} - m + \frac{2m}{3} = 0,$$

which yields a contradiction.

We shall assume that this is true for all planar graphs or order $< n$, and we shall show that it is true for a planar graph $G$ or order $n$.

From the first question, there exists a vertex $x_0$ with degree $\leq 5$. We can colour the graph $G_{X-\{x_0\}}$ with the six colours $\alpha_1$, $\alpha_2$, $\alpha_3$, $\alpha_4$, $\alpha_5$, $\alpha_6$. The colour for vertex $x_0$ can be chosen without difficulty. In the worst case, $d_G(x_0)=5$ and all the 5 vertices $y_1$, $y_2$, $y_3$, $y_4$, $y_5$ adjacent to $x_0$ all have different colours. In that case, we choose the 6th colour for $x_0$.

Therefore, $G$ is 6-colourable.