TITLE: Every face in a maximal triangle free planar graph is a quadrilateral or a pentagon
QUESTION [1 upvotes]: 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?

REPLY [2 votes]: 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

the path can't go through the face (we need that to remain a face),
the path can't intersect any $p_i$ on an edge (because the graph is planar),
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$.
{"set_name": "stack_exchange", "score": 1, "question_id": 2003095}