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 planar minimal 5-chromatic graph. That is, any of its proper subgraphs has chromatic number at most 4. I need to prove that its minimum degree is at least 5. I want to prove by contradiction, first by assuming that there is a vertex of degree 4. But I couldn't find any contradiction. Can anyone offer any ideas?

share|improve this question
2  
This doesn't seem right. The $4$-color theorem implies that all planar graphs satisfy this property. –  EuYu May 21 '13 at 23:39
1  
Is it possible that you mean $5$-choosable and are talking about list chromatic number? Or are you proving a condition on a (hypothetical) planar graph of chromatic number $5$, assuming one exists? –  Andrew Salmon May 22 '13 at 0:19
    
It true that the four colour theorem says these won't exist, but the four colour theorem is mathematically hard to prove, whereas this ought to be doable with elementary techniques and no computerised checking - in fact, it may be necessary to prove it on the way to proving the four colour theorem, although I don't actually know if that is the case. (Sadly, tried the question and also stuck...) –  meta May 27 at 9:52

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.