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've been tasked to prove that there can be no planar graph with 5 faces, such that any two of them share an edge.

I've been able to come up with the proof quite easily, but the teacher said this problem is supposed to be extremely hard. So, now I'm doubting the validity of my proof and hoping someone could check it.

The proof:

Assume the contrary, let there exist such a graph $G$. Since $G$ is planar, we can build a graph $G^*$ dual to $G$. Any two faces in $G$ share an edge $\implies$ any two faces in $G$ are adjacent $\implies$ any two vertices in $G^*$ are also adjacent (by the property of dual graphs). Since $G$ has 5 faces, $G^*$ has 5 vertices. So, $G^*$ is a complete graph on five vertices which might contain loops and parallel edges. Obviously, $K_5$ is a subgraph of $G^*$. Therefore, by Kuratowski's theorem, $G^*$ cannot be planar, which contradicts the property of dual graphs (a graph dual to a planar graph is also planar). Q.E.D.

Well, that's it. I really hope someone could comment on this proof, and correct it, if it's wrong. Thank you!

share|improve this question
5  
Your argument is sound. Sometimes people mistakenly believe the statement in your title is equivalent to the 4-color theorem, so maybe that is the source of the confusion about difficulty? –  Grumpy Parsnip Mar 9 '12 at 18:17
1  
The argument works. –  Daniel Montealegre Mar 9 '12 at 20:04
1  
Teachers make mistakes, too (and I speak from personal experience). –  Gerry Myerson Mar 10 '12 at 5:43
1  
Would you be willing to post your own answer and then accept it? –  Graphth Mar 14 '12 at 16:21
    
@Graphth I didn't know you could do that. Sure. –  user825089 Mar 14 '12 at 20:12

1 Answer 1

up vote 4 down vote accepted

I turned in my proof and the teacher said it is correct, so here it is again:

Assume the contrary, let there exist such a graph $G$. Since $G$ is planar, we can build a graph $G^*$ dual to $G$. Any two faces in $G$ share an edge $\implies$ any two faces in $G$ are adjacent $\implies$ any two vertices in $G^*$ are also adjacent (by the property of dual graphs). Since $G$ has 5 faces, $G^*$ has 5 vertices. So, $G^*$ is a complete graph on five vertices which might contain loops and parallel edges. Obviously, $K_5$ is a subgraph of $G^*$. Therefore, by Kuratowski's theorem, $G^*$ cannot be planar, which contradicts the property of dual graphs (a graph dual to a planar graph is also planar). Q.E.D.

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.