Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
That is not what 3-colourable means. –  Chris Eagle Nov 22 '12 at 18:18

2 Answers 2

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.

share|improve this answer
    
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. –  Graphth Nov 23 '12 at 15:53

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 \leq 3v$, contradicting 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.]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.