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.

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable.


I'm not too sure how to approach this one and I really need to get better with proofs. But anyway, I know from a previous exercise that the faces of $G$ cannot be bounded by more than 4 edges. More specifically, $m \leq 3f - 6$ where $m$ is the number of edges and $f$ is the number of faces in the graph $G$. However, I'm not sure where to go from here. Any help would be appreciated.

share|improve this question
    
I haven't checked the details, so this is just a suggestion. You can show using Euler's formula and the Handshaking Lemma that a $G$ satisfying your hypotheses must have a vertex of degree at most $4$. Now try to imitate the proof of the $5$-Color Theorem. –  Casteels Apr 14 at 12:12

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.