1
$\begingroup$

A maximal triangle free planar graph is a graph such that if we add one edge that's not in the original graph, the resulting graph contains a triangle or is non-planar. Show that every face in a maximal triangle free planar graph is a is a quadrilateral or a pentagon.

It's easy to see that a single face with more than 5 edges is not 'maximal' since we can connect two vertices without creating a triangle. But how do we use this fact to show the claim? Any idea?

$\endgroup$
2
$\begingroup$

Doesn't what you said prove the claim? No, it's tougher than that.

Suppose for the sake of contradiction that $G$ is a maximal triangle-free planar graph with a face bounded by at least six edges. Then we can find two vertices on that face that differ by at least a path of length three*. Joining these two vertices with an edge, the resulting graph is still triangle-free and planar, contradicting $G$ being maximal.


* This is not immediately obvious since there may be a path of length two between the two vertices that is not part of the boundary of the face. But to see why this is true, note that there must be at least three pairs of "opposite" vertices to be connected on the face bounded by at least six vertices. Suppose that each possible pair of opposing vertices$\dagger$ but one is connected by a path $p_i$ of length two, where the other vertex on the path is named $v_i$.

Now take a final possible opposing pair of vertices $a$ and $b$ on the boundary of the face. These two are not connected by a path of length two because

  1. the path can't go through the face (we need that to remain a face),
  2. the path can't intersect any $p_i$ on an edge (because the graph is planar),
  3. and the path can't go through any $v_i$ (because this would form a triangle since one of the vertices $a$ or $b$ will be adjacent to another vertex in a previous opposing pair).

So we may safely connect $a$ and $b$ with an edge without fear of forming a triangle.


$\dagger$ There's some hand-waving here, but it really hardly matters how you pick all these opposing pairs. You don't even necessarily need to pick all but one possible opposing pair here. You only need this to guarantee that a triangle gets formed if a path between $a$ and $b$ goes through $v_i$.

$\endgroup$
  • $\begingroup$ That's what I initially thought. But how do we know that this new edge $e$ won't create a triangle with two other edges outside of the face? $\endgroup$ – user112358 Nov 7 '16 at 5:46
  • $\begingroup$ Oh, that is a little more complicated than I suspected. But I think drawing the minimal case, a $6$-cycle where each pair of opposite edges is connected by a path of length two, helps to see why the claim is still true. I'll edit my answer accordingly. $\endgroup$ – Mike Pierce Nov 7 '16 at 5:51
  • $\begingroup$ I've added a explanation, but I'm afraid it isn't completely clear (I wish I could draw images on MathSE more easily). Please ask if there is anything unclear in my explanation. $\endgroup$ – Mike Pierce Nov 7 '16 at 6:11
  • $\begingroup$ Let's say we draw a hexagon face with 3 opposing pairs of vertices. But when I draw the second path there is no way that the second path won't cross the first path without going inside of the hexagon. $\endgroup$ – user112358 Nov 7 '16 at 6:28
  • $\begingroup$ @Lewis Yeah, so in many cases you don't need to connect all but one possible set of opposing pairs of vertices, but if you can connect all of them, you can't connect the last one. That seemed like an easier line of proof. $\endgroup$ – Mike Pierce Nov 7 '16 at 6:56

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.