Graph Theory Question: Is it possible to prove that the four-color theorem holds true for a generic planar graph with seven vertices?

Question

This question comes from the book An Introduction to Graph Theory (Page 140 for me).

The book asks if it is possible, noting the five color theorem (I am aware of the four color theorem but five color is more useful here) holds true for planar with vertices less than or equal to 5, the theorem holds true for problems with 6 vertices because every graph has at least one vertex with a degree 4 so by Theorem 3 it also has X (chromatic number) is less than or equal to 4, that the theorem holds true for a problem with 7 vertices.

I don't know how helpful this next part is because I have know way of relating the number of edges, vertices, or faces to the chromatic number but there are several things I can derive.

• v (the number of vertices)=7
• the graph is planar so we have the following formula's available to us
• The number of edges (e) of a graph is $e=(1/2)v(v-1)$ ($e=(1/2)*(7)*(7-1)$), so $e=21$
• Euler's formula tells us that $v+f-e=2$ ($7+f-21=2$), so $f=16$

I would love some help if anyone is able?

Answer 1

The smallest counterexamples to Kempe's flawed proof of 5CT$\to$4CT (the Fritsch graph and the Soifer graph) have nine vertices. So Kempe's relatively straightforward argument would work on any planar graph with seven vertices.

Answer 2

1. If the degree of every vertex is at most $n-1$ then we can obviously colour the vertices with $n$ colours. So any graph (planar or not) with 4 points or less can be 4-coloured.

2. Next we need a result known as Brooks' Theorem : any graph all of whose vertices have degree less than or equal to $n$ can be vertex-coloured with $n$ colours, except for the complete graphs and odd cycle graphs (ie the graphs where the only edges form a single loop). There is a proof sketch in Wikipedia and a fuller proof here and probably in the book you are reading. Any cycle graph can be vertex-coloured with 3 colours. So Brooks' Theorem implies that any planar graph all of whose vertices have degree 4 or less can be vertex-coloured with 4 colours.

3. Any graph with 5 vertices has every vertex of degree 4, so Brooks' Theorem tells us it can be vertex-coloured with 4 colours.

4. Now suppose $G$ has 6 vertices. If every vertex has degree 4 or less then we can use Brooks' Theorem. If any vertex $V$ has degree 3 or less, then we can 4-colour the other five and then pick a colour for $V$ different from its neighbours. So the remaining case is where one vertex $V_1$ has degree 5 and the others degree at least 4.

5. No four of the others can have every edge between them (or they and $V_1$ would form a complete and hence non-planar graph). So assume $V_2,V_3$ are not joined by an edge. They both have degree at least 4, so they are both joined to each of $V_4,V_5,V_6$. So the graph is non-planar (it includes edges forming a $K_{3,3}$ graph with $V_1,V_2,V_3$ and $V_4,V_5,V_6$ as the two groups of 3).

6. We come finally to a graph with 7 vertices. As in the case of 6 vertices, we only need to deal with the case where one vertex, say $V_1$, has degree 5 or more, and the others have degree 4 or more. Suppose first that $V_1$ has degree 6. If any of $V_2,\dots,V_7$ have degree 6, then none of the other can have degree 5. For suppose $V_2$ has degree 6, and $V_3$ degree 5. Then $V_3$ is joined to three of $V_4,V_5,V_6,V_7$ and $V_1,V_2$ are joined to all of them, so we have a $K_{3,3}$ subgraph and the graph is non-planar. So assume $V_1,V_2$ have degree 6 and the other vertices have degree 4. Then if we consider the subgraph of $V_3,\dots,V_7$ each vertex has degree 2. A little thought shows that it must be a cycle, so we have this situation:

7. For clarity the graph does not show edges from $V_1$ or $V_2$. But now we have a $K_{3,3}$ structure with the red vertices $V_1,V_3,V_5$ and the green vertices $V_2,V_4,V_6$. The path from $V_3$ to $V_6$ is indirect via $V_7$ the others are direct. So the graph is non-planar. Hence we can assume that only $V_1$ has degree 6, and the other vertices all have degree 4 or 5.

But I don't want to take away all your fun, so @Tom maybe after these pointers you can see how to complete the case of 7 vertices? If not, I will add to this tomorrow.

Answer 3

The proof of the five-colour theorem works by induction on $n$, the number of vertices: remove a vertex $x$ of minimum degree, colour the remaining graph, and try to find a colour for the vertex you removed. Using Euler's formula you can show that $e\leq 3n-6$, and in particular (via handshaking), the minimum degree is at most $5$. The only problem comes if $x$ has degree exactly $5$ and the adjacent vertices all get different colours. In this case you can find a suitable Kempe chain to swap colours on, making two of the adjacent vertices the same colour and leaving a colour available for $x$.

If you knew somehow that $x$ had degree at most $4$, and that the same was true for all smaller graphs, then exactly the same proof would work but with four colours instead of five. But actually this is true if $n\leq 11$: $e\leq 3n-6$ means that any planar graph with $n\leq 11$ has minimum degree at most $4$. So this method can prove that all such graphs are $4$-colourable.