Prove that every plane triangulation has at least $n(n \ge 4)$ edges $e$ with the property that the only triangles containing $e$ are faces.

Question

I am trying to prove the following theorem.

Theorem Every maximal planar graph of order 4 or more is 3 connected.

I looked up similar questions(prove-that-every-maximal-planar-graph-of-order-4-or-more-is-3-connected) and found that Raoul provided a detailed answer details.pdf with the help of the following lemma.

Lemma Every plane triangulation with $n ≥ 4$ vertices has at least $n$ edges $e$ with the property that the only triangles containing $e$ are faces.

I did not understand one of the steps of the proof.

Thus, at most $3$ edges with the desired property are lost in the
combining, leaving us with $|V_1| + |V_2| − 3 = n$ such edges, as desired.

I feel that if all edges on $t$ satisfy the property the only triangles containing them are faces
whether inside or outside.
Then it should become at least $|V_1| + |V_2| − 6$ in the combining not $|V_1| + |V_2| − 3$.

For example, in graph G below, we choose $C_3= uvw$, Any edge of the circle satisfies the condition in $C^{int}$ and $C^{out}$ but all lose the desired property in $G$.

If this lemma is incorrect, how should the theorem be proved?

In order to eliminate the confusion caused by the possible invalidation of the pdf file link, I re-copy the reference answer here.

Fix an embedding of the triangulation.

First, we prove that every plane triangulation with $n ≥ 4$
vertices has at least $n$ edges $e$ with the property that the only
triangles containing $e$ are faces. The proof is by induction on
$n$ . The base is case is $K_4$ and holds trivially because all $6$
edges have this property.

For the induction, pick any triangle $t$ that is not a face. We split
the graph into two parts, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ ,
where $G_1$ is the induced graph on $t$ and all of the vertices
inside $t$ in the embedding and $G_2$ is the induced graph on $t$
and all of the vertices outside $t$ . Both graphs are plane
triangulations and both have fewer than n vertices. So, by induction,
there are $|V_1| + |V_2| = n + 3$ edges in the two graphs with the
desired property. When we combine the graphs, the only edges that can
lose this property are the edges of $t$ because no edges pass between
any of the other vertices of to any of the other vertices of $G_2$ .
Thus, at most $3$ edges with the desired property are lost in the
combining, leaving us with $|V_1| + |V_2| − 3 = n$ such edges, as
desired.

Answer 1

I agree that the proof of the lemma is bad. The lemma might still be true, but I don't see how to prove it offhand.

I don't think we need the full power of the lemma. It's enough to show that:

Lemma. Every plane triangulation with $n \ge 4$ vertices has at least $6$ edges $e$ with the property that the only triangles containing $e$ are faces.

Proof. We do the same induction, except that $G_1$ and $G_2$ both contain $6$ of these edges. $3$ of those edges in $G_1$ might be edges of $t$ (so they don't count), and the same for $G_2$, but that still leaves $3$ edges in $G_1$ and $3$ in $G_2$ that do count, for a total of $6$. $\square$

We can carry out the proof that all plane triangulations with $n\ge 4$ vertices are $3$-connected, even if we only have the weaker version. All we need is that:

• If $\{u,v\}$ is a cut of $G$, then we don't contract edge $uv$.
• If we can partition $V(G)-\{u,v\}$ into $X \cup Y$ with no edges between $X$ and $Y$, then we shouldn't destroy the last vertex of $X$ or $Y$ (by contracting an edge incident to that vertex).

The first only excludes one edge at any moment. The second one doesn't constrain us at all unless $|X|=1$ or $|Y|=1$. But first of all, if $X = \{x\}$, that's at most two edges: $xu$ and $xv$ (and two more if $Y = \{y\}$). Second, I don't think that can actually happen, because at that point, the graph is pretty blatantly not a triangulation.

So having $6$ edges we can choose from to contract at any time is plenty to complete the proof.