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