Find the mistakes in a "proof" of the 4-colour Theorem

155 Views Asked by At

I am working on the following exercise:

Find all mistakes in the following “proof” of the Four Colour Theorem.

Suppose, for contradiction, that the Four Colour Theorem is false. Let $v$ be a vertex of degree $d := δ(G) \le 5$ in a smallest non-4-colourable planar graph $G$. Fix a drawing of $G$ and a 4-colouring $c$ of $G-v$. Denote the neighbours of $v$ by $x_1, \ldots , x_d$ in the order they lie around $v$ in the drawing. Furthermore, set $G_{i,j} := G[c^{−1}(i) \cup c^{−1}(j)]$. Since $G$ is not 4-colourable, we know that

no 4-colouring of $G-v$ uses less than four colours for $N(v)$. (1)

In particular, $d \ge 4$. Without loss of generality, we may assume that $c(x_i) = i$ for $i = 1, 2, 3, 4$ and, if $d = 5$, then $c(x_5) \in {1, 2}$.

Suppose first that $d = 4$. If there is no $x_1–x_3$ path in $G_{1,3}$, then we can recolour $x_1$ with colour $3$ by exchanging the colours in the component of $G_{1,3}$ that contains $x_1$ and obtain a colouring $c'$ that contradicts (1). Otherwise, $G_{2,4}$ contains no $x_2–x_4$ path and thus we can recolour $x_2$ with colour $4$, contradicting (1).

Now suppose that $d = 5$ and $c(x_5) = 1$. If there is no $x_3–\{x_1, x_5\}$ path in $G_{1,3}$, we can recolour $x_3$ with colour $1$. Otherwise, we can recolour $x_2$ with colour $4$ as in the case $d = 4$. Either way, we construct a colouring of $G-v$ that contradicts (1).

Finally, suppose that $d = 5$ and $c(x_5) = 2$. If there is no $x_1–x_3$ path in $G_{1,3}$ or no $x_1–x_4$ path in $G_{1,4}$, then we can recolour $x_1$ with colour $3$ or $4$, respectively, and get a contradiction to (1). Otherwise, there is neither an $x_2–x_4$ path in $G_{2,4}$ nor an $x_5–x_3$ path in $G_{2,3}$. Thus, we can recolour $x_2$ with colour $4$ and $x_5$ with colour $3$, again a contradiction to (1).

My commentary: We know that $G$ contains a vertex with degree $\le$ 5 since $G$ has to be planar by the 4 colour theorem.

Do you see any other errors?