The Simple Planar Edge Bound

Why Planarity Limits the Number of Edges

A plane drawing of a graph divides the plane into faces, and the boundary of each face uses edges of the graph. In a connected simple planar graph with at least three vertices, every face boundary has length at least three. At the same time, every edge contributes exactly two edge-sides to the face boundaries. These facts let us compare the total boundary length with the number of edges. Euler’s formula then turns that comparison into an upper bound on the number of edges.

A graph is planar if it can be drawn in the plane with no edge crossings except at shared endpoints. A particular crossing-free drawing is a plane embedding. Its faces are the regions of the plane left after removing the drawing, including the unbounded region. The length of a face boundary is the number of edge occurrences in its boundary walk. If an edge appears twice in that walk, it is counted twice. This matters for bridges: a bridge has the same face on both sides, so its two edge-sides both contribute to a face-boundary length.

We use Euler’s formula for connected plane graphs: if a connected plane graph has \(n\) vertices, \(m\) edges and \(f\) faces, then \(n-m+f=2\). Our goal is to combine that formula with the boundary-length count. The graph must be connected, simple, and have at least three vertices; the conclusion below is stated only under these hypotheses.

Face Lengths and Edge-Sides

Proof. A face boundary walk of length \(1\) would use a loop, which a simple graph does not have. Consider a boundary walk of length \(2\). If its two edge occurrences were distinct edges joining the same two vertices, the graph would have multiple edges. Thus the walk would have to traverse one edge \(uv\) from \(u\) to \(v\) and immediately traverse it back from \(v\) to \(u\). In tracing a face boundary, an immediate reversal at an endpoint can occur only when that endpoint has degree \(1\): otherwise the boundary continues along another incident edge in the cyclic order of the embedding. So both \(u\) and \(v\) would have degree \(1\). Since the graph is connected, it would consist only of \(u,v\) and the edge \(uv\), contradicting the assumption that it has at least three vertices. Boundary length \(0\) is not possible here, since the connected graph has edges. Therefore every face boundary has length at least \(3\). \(\square\)

Now count the total length of all face boundaries. Each edge has two sides, and each side occurs once in the boundary-walk count. The two sides may belong to two different faces, or both may belong to the same face when the edge is a bridge. In either case, counting with multiplicity gives total boundary length \(2m\).

If there are \(f\) faces, the lemma says that each of the \(f\) terms in this sum is at least \(3\). Hence \(2m\geq 3f\). This is the face estimate that will be paired with Euler’s formula.

The Simple Planar Edge Bound

Proof. Since \(G\) is planar, choose a plane embedding. Write \(f\) for its number of faces. The face-length count gives \(2m\geq 3f\). Euler’s formula gives \(n-m+f=2\), so \(f=2-n+m\). Substitute this expression for \(f\) into the inequality:

Subtract \(3m\) from both sides to obtain \(-m\geq 6-3n\). Multiplying by \(-1\) reverses the inequality, giving \(m\leq 3n-6\), as claimed. \(\square\)

The estimate uses two different ingredients. Simplicity and \(n\geq 3\) ensure that face boundaries cannot be too short, while connectedness allows Euler’s formula in the form \(n-m+f=2\). The argument applies to a connected planar graph by choosing any plane embedding of it; it does not require that a particular drawing be supplied.

Proof. Euler’s formula rearranges to \(f=2-n+m\). Applying the theorem’s bound \(m\leq 3n-6\) gives \(f\leq 2-n+(3n-6)=2n-4\). \(\square\)

Worked Checks

A Common Counting Error

A frequent mistake is to count each edge only once when adding face-boundary lengths. For the triangle with pendant edge above, that would incorrectly give total boundary length \(m=4\). The actual face lengths are \(3\) and \(5\), so the total is \(8=2m\). The bridge \(cd\) appears twice on the unbounded face boundary because the same face lies on both sides of the bridge.

The mistake can also lead to an invalid inequality. If one incorrectly used \(3f\leq m\), then in this example \(3f=3\cdot2=6\) would have to be at most \(m=4\), which is false. The valid estimate is \(3f\leq2m\), because each edge contributes two sides. Keeping the multiplicity in boundary walks is essential to the proof.

The hypotheses matter as well. The theorem is not asserted here for disconnected graphs, graphs with loops or multiple edges, or graphs with fewer than three vertices. In particular, a face boundary of length \(2\) can occur for a connected simple graph consisting of a single edge, but that graph has only two vertices. The proof’s face-length lemma relies on excluding that case.