Triangulations and Equality in the Planar Edge Bound

When Does a Plane Graph Reach the Edge Bound?

For a simple planar graph with at least three vertices, the upper bound $m\le 3n-6$ is sharp: some plane embeddings attain it exactly. The face boundaries explain precisely when this happens. Each face must use the minimum possible number of edge-sides, namely three. The conclusion concerns every face, not just the presence of a few triangular regions.

Throughout, graphs are finite and simple. A plane graph is a graph together with a particular drawing in the plane in which edges meet only at shared endpoints. Its faces are the regions of the complement of that drawing, including the unbounded region. The boundary walk of a face records its successive edge-sides; a bridge is counted twice if the boundary walk traverses it in both directions. The length of a boundary walk is its number of edge-sides, counted with these repetitions.

Definition: A plane triangulation is a connected plane graph in which the boundary walk of every face is a cycle of length $3$. A graph is maximal planar if it is planar and adding any edge between two previously nonadjacent vertices makes it nonplanar.

In a connected plane graph, each edge contributes two sides to face boundaries, one on each side of the drawing. Thus, if the face boundary lengths are $\ell_1,\ldots,\ell_f$, then $\sum_{i=1}^{f}\ell_i=2m$. We also use Euler’s formula for connected plane graphs, $n-m+f=2$. Both statements apply to boundary walks, including when a bridge is repeated.

The Equality Characterization

For a connected simple plane graph with $n\ge3$, every face boundary walk has length at least $3$. Length $1$ would require a loop. A length-$2$ boundary walk in a simple graph would have to traverse one edge in both directions; for that edge to be the entire boundary walk, both endpoints have degree $1$. Connectedness would then make the graph a single edge, contrary to $n\ge3$. Consequently, $2m=\sum_i\ell_i\ge3f$. Combining this incidence count with Euler’s formula gives the edge bound and, more importantly here, its exact slack.

3n-6-m =3(n-m+f)-6+(2m-3f) =2m-3f =\sum_{i=1}^{f}(\ell_i-3).

Theorem: Let $G$ be a connected simple plane graph with $n\ge3$, $m$ edges and face-boundary lengths $\ell_1,\ldots,\ell_f$. Then $$ m\le 3n-6, $$ with equality if and only if every face boundary is a triangle. Equivalently, equality holds if and only if the given embedding is a plane triangulation.

Proof. The length bound just established gives $\ell_i-3\ge0$ for every face. The displayed slack identity therefore gives $3n-6-m\ge0$, which is $m\le3n-6$. If $m=3n-6$, the slack is zero, so $\sum_i(\ell_i-3)=0$. A finite sum of nonnegative integers is zero only when every summand is zero; hence each $\ell_i=3$. Conversely, if every $\ell_i=3$, then each term in the sum is zero, so the slack identity gives $3n-6-m=0$, or $m=3n-6$. In a simple graph, a closed boundary walk of length $3$ has three distinct vertices: a repeated vertex would force a loop. Thus each such boundary walk is a 3-cycle, as required by the definition of a plane triangulation. $\square$

The identity also measures how far an embedding is from equality. Each face of length $4$ contributes $1$ to the difference $3n-6-m$; each face of length $5$ contributes $2$, and so on. This is a direct count of the nontriangular boundary length in excess of three per face.

Worked Embeddings

Worked Example: The Triangular Embedding of K4

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,31,14,24,34\}$. Embed $1,2,3$ as an outer triangle and place $4$ inside it, joining $4$ to each of $1,2,3$. The four faces have boundary cycles $123$, $124$, $234$, and $314$.

There are $n=4$ vertices and $m=6$ edges. Substitution in the edge bound gives $3n-6=3(4)-6=12-6=6=m$. The face count from Euler’s formula is $f=2-n+m=2-4+6=4$, agreeing with the four listed faces. Their total boundary length is $3+3+3+3=12$, and the edge-side count gives $2m=2(6)=12$.

Check: Each of the four face boundaries has length $3$, so the equality criterion applies. The graph is $K_4$, so every pair of its vertices is already adjacent; no edge can be added while keeping the graph simple. It is therefore maximal planar.

Worked Example: A Five-Vertex Plane Triangulation

Let $G$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,31,14,24,34,15,25,35\}$. Draw the triangle $123$, put vertex $4$ on one side of it and vertex $5$ on the other, and join each of $4$ and $5$ to all three vertices of the triangle. The faces are $124$, $234$, $314$, $125$, $235$, and $315$, each a 3-cycle.

Counting the displayed edges gives $m=9$, and $n=5$. The bound is $3n-6=3(5)-6=15-6=9$, so equality holds. Euler’s formula gives $f=2-5+9=6$, matching the six listed faces. Their boundary lengths sum to $6(3)=18$, while $2m=2(9)=18$, independently checking the face count by edge-sides.

Check: The only missing pair of vertices is $45$. Adding that edge while retaining planarity would produce a simple planar graph on five vertices with $10$ edges. But the bound gives at most $3(5)-6=9$ edges for any simple planar graph on five vertices. Therefore $45$ cannot be added planarly, and this graph is maximal planar.

Worked Example: One Nontriangular Face and the Exact Slack

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41,13\}$. Draw the 4-cycle $1,2,3,4,1$ as the outer boundary and draw diagonal $13$. The faces have boundary cycles $123$ and $134$, and the outer face has boundary walk $1,2,3,4,1$. Their lengths are $3,3,4$.

Here $n=4$ and $m=5$, so $3n-6=3(4)-6=6$, and the shortfall is $6-5=1$. The boundary excess is $(3-3)+(3-3)+(4-3)=0+0+1=1$, exactly the same shortfall. Also, $f=2-4+5=3$, and the sum of boundary lengths is $3+3+4=10=2(5)=2m$.

Check: The outer face has length $4$, so not every face is triangular and the equality criterion rules out equality. The direct edge count agrees: $5<6$. This example shows why an embedding with some triangular faces is not enough.

Maximality and What Equality Certifies

For $n\ge3$, equality in the edge bound also certifies maximal planarity. If a simple planar graph has $m=3n-6$ edges, adding an edge between any nonadjacent vertices would leave the order unchanged and raise the size to $3n-5$. The planar edge bound forbids that for a simple planar graph of order $n$. Thus no such edge can be added while retaining planarity. This argument uses the bound as a necessary condition; it does not require an analysis of which face the new edge might cross.

For a connected plane graph, the face criterion gives more information than the edge count alone: equality in that particular embedding forces every face boundary to be triangular. Conversely, a connected simple plane graph with triangular face boundaries has exactly $3n-6$ edges and is maximal planar. The five-vertex example illustrates the converse maximality check as well: its equality leaves no room for an additional planar edge.

For a disconnected simple planar graph with $n\ge3$, equality cannot occur. One can join its components one at a time by drawing an edge between distinct components through a common face, preserving planarity and simplicity. If there are $c\ge2$ components, this produces a connected simple planar graph on the same $n$ vertices with $m+c-1$ edges. Applying the connected bound gives $m+c-1\le3n-6$, hence $m\le3n-5-c\le3n-7<3n-6$. Thus any simple planar graph attaining the bound must be connected, and its plane embeddings have the triangular-face characterization above.

Common Face-Counting Pitfalls

Counting an edge only once. The face-boundary sum counts edge-sides, not edges. In the $K_4$ embedding, $m=6$, but the total face-boundary length is $12$, not $6$: each of the six edges contributes two sides. The correct check is $2m=12=3f$, since there are four triangular faces.

Checking only the bounded faces. The unbounded face is still a face and must be included. In the four-vertex example with diagonal $13$, the two bounded faces are triangles, but the outer boundary has length $4$. Omitting it would falsely suggest that all faces are triangular and would give an incorrect equality conclusion.

Confusing “has triangles” with “is a triangulation.” The equality condition requires every face boundary to have length $3$. A single face of length greater than $3$ contributes positive slack, so the edge bound is then strict.

Check Your Understanding

Use boundary lengths and the slack identity to justify your answers.

A connected simple plane graph has $n=6$ vertices and face-boundary lengths $3,3,3,4,5$. Find $m$ using Euler’s formula and the edge-face incidence count, then compute its shortfall from $3n-6$.
Explain why a connected simple plane graph of order at least three cannot have a face boundary walk of length $2$.
Prove that if a connected simple plane graph with $n\ge3$ has $m=3n-6$, then it is maximal planar.
For the five-vertex graph in the second worked example, list its missing vertex pairs and use the edge bound to verify maximality.
Why does an embedding with three triangular faces and one face of length $4$ fail to attain equality?