2
$\begingroup$

I'm having trouble with this question. I need to prove that all connected planar graphs with girth at least 6 are 3-colourable.

I know that a girth of 6 means that the smallest cycle in a graph is 6 edges. I also know that a 3-colourable means we need at least 3 colours such that no adjacent vertices are the same colour.

  • 5
    That is not what 3-colourable means.2012-11-22

2 Answers 2

5

Here's a self-contained, fairly elementary proof.

As is typical, let $v$, $e$ and $f$ denote the number of vertices, edges and faces in $G$, respectively.

Firstly, the result is true when $v \leq 5$, since, in these cases, $G$ has no cycles, and is thus bipartite and thus 2-colourable (and thus 3-colourable). So, we can assume $v \geq 6$.

Lemma 1: $2e \geq 6f$.

Proof: Every edge is adjacent to at most $2$ faces, and every face is adjacent to at least $6$ edges (since $v \geq 6$). So the number $P$ of $(\text{face},\text{adjacent edge})$ pairs is at most $2e$ and at least $6f$. Hence $2e \geq P \geq 6f$. [End of proof.]

Lemma 2: $2e \leq 3v-6$.

Proof: Apply Euler's Characteristic Formula to Lemma 1. \begin{align*} 2e & \geq 6f & \text{by Lemma 1} \\ & = 6(e-v+2) & \text{by Euler's Characteristic Formula} \end{align*} which rearranges to give the claimed result. [End of proof.]

Lemma 3: $G$ has a vertex of degree at most $2$.

Proof: If not, every vertex in $G$ has degree at least $3$, and, by the Handshaking Lemma, $2e \geq 3v$, which contradicts Lemma 2. [End of proof.]

And finally:

Theorem: If $G$ is a planar graph with girth at least 6, then $G$ is $3$-colourable.

Proof: We proceed by induction on $v$. The result is true when $v=5$ (as previously mentioned, so assume $v \geq 6$.

By Lemma 3, $G$ has a vertex $x$ of degree at most $2$. By the inductive hypothesis, $G \setminus x$ can be $3$-coloured. Since $x$ has degree at most $2$, we can extend any $3$-colouring of $G \setminus x$ to a $3$-colouring of $G$ (we simply assign $x$ a colour not used by its neighbour[s]). [End of proof.]

1

Every triangle-free planar graph is 3-colorable. This is known as Grötzsch's theorem. Additionally, 3-colorable just means that you can color the vertices with 3 colors. The condition of needing at least 3 colours such that no adjacent vertices are the same colour is known as a chromatic number of 3.

  • 1
    I learned something new, so thanks. But, other than that, is this very helpful? It seems to me as if the OP has a homework question and is trying to solve it. Is quoting a much stronger result helpful? The Wikipedia article says the proof is complex and that an attempt by Berge to simplify it resulted in an erroneous proof. So, certainly, such a proof would not be expected on OP's homework. So, this doesn't answer the OP's question at all. It's a good answer in that if someone else comes here to look at this question, they too may learn something.2012-11-23