# Proof that there can be no planar graph with 5 faces, such that any two of them share an edge.

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!

-
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
The argument works. –  Daniel Montealegre Mar 9 '12 at 20:04
Teachers make mistakes, too (and I speak from personal experience). –  Gerry Myerson Mar 10 '12 at 5:43
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. –  ivt Mar 14 '12 at 20:12

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.