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.

(1) Prove that the Groetzsch Graph is not planar.

share|improve this question

closed as off-topic by Daniel Rust, T. Bongers, Serkan, Eric Naslund, Bruno Joyal Nov 25 '13 at 3:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Daniel Rust, T. Bongers, Community, Eric Naslund, Bruno Joyal
If this question can be reworded to fit the rules in the help center, please edit the question.

    
4-colour-theory is difficult, 2-coour theory is easy. –  Hagen von Eitzen Nov 20 '13 at 7:24
    
ad (2): One cannot colour the faces of a cube with two colours only!! –  Hagen von Eitzen Nov 20 '13 at 7:25

1 Answer 1

up vote 0 down vote accepted

For (1) recall that a graph is non-planar if and only if it contains a subgraph that is a subdivision of either $K_5$ or $K_{3,3}$. So can you find such a subgraph? (Hint: $K_5$ works for this case).

Something seems to be wrong with (2). Consider three "countries" where each two share a border (e.g., Oregon, Nevada and California). You clearly need three colors.

share|improve this answer
    
Could you explain a bit more for 1? I feel like my professor expected an algebraic proof, which I didn't do unfortunately. And yeah, I think he made a mistake with question 2. –  Jay C Nov 24 '13 at 11:21
    
@Jay C Oh ok. Well one thing that follows from Euler's formula are upper bounds on the number of edges in terms of the number of vertices. Try one of these. –  Casteels Nov 24 '13 at 19:35

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