7
$\begingroup$

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!

$\endgroup$
  • 5
    $\begingroup$ 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? $\endgroup$ – Cheerful Parsnip Mar 9 '12 at 18:17
  • 1
    $\begingroup$ The argument works. $\endgroup$ – Daniel Montealegre Mar 9 '12 at 20:04
  • 1
    $\begingroup$ Teachers make mistakes, too (and I speak from personal experience). $\endgroup$ – Gerry Myerson Mar 10 '12 at 5:43
  • $\begingroup$ @Graphth I didn't know you could do that. Sure. $\endgroup$ – ivt Mar 14 '12 at 20:12
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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