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!
Best Answer
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.