Why Girth Restricts the Number of Edges
Euler’s formula links the numbers of vertices, edges and faces in a connected plane graph. Girth supplies another constraint: when every face-boundary walk has length at least \(g\), the total number of edge-face incidences forces a bound on the number of edges. The key is to state the hypotheses carefully. A face boundary can traverse a bridge twice, so a lower bound based on cycle length requires that the graph have no bridges.
All graphs in this tutorial are finite and simple. A plane graph is a graph together with a fixed drawing in the plane in which edges meet only at common endpoints. A face is a region of the drawing’s complement. A face-boundary walk follows the edges bordering that face, counting an edge each time it is traversed. The girth \(g(G)\) of a graph containing a cycle is the length of its shortest cycle.
We will consider connected, bridgeless plane graphs with at least one edge. For a connected graph, an edge is not a bridge exactly when its endpoints remain connected after the edge is deleted. Thus each edge of a connected bridgeless graph lies on a cycle: an alternative path between its endpoints, together with the edge, contains a cycle. Since the graph is simple, that cycle has length at least \(3\). In particular, such a graph has \(n\ge 3\) and its girth is defined and satisfies \(g\ge 3\).
Face Boundaries and Girth
For a connected plane graph, a bridge is traversed twice in the boundary walk of its incident face; a non-bridge edge has its two sides incident with distinct faces. These are the bridge and face-boundary facts established in the earlier material on bridges and repeated face boundaries. Therefore, in a bridgeless connected plane graph, no face-boundary walk repeats an edge. Each such walk is a closed trail: it is closed and has no repeated edges.
Proof. Write the closed trail as \(v_0v_1\cdots v_L\), where \(v_L=v_0\), and choose indices \(i<j\) with \(v_i=v_j\) so that \(j-i\) is as small as possible among such pairs. The section from \(v_i\) to \(v_j\) has no repeated interior vertex, by the minimality of \(j-i\). Its length cannot be \(1\), because the graph has no loops. Its length cannot be \(2\), because then the section would traverse the same undirected edge twice, contradicting that the walk is a trail. Hence this section is a cycle of length \(j-i\), which is at most \(L\). \(\square\)
Apply the lemma to a face-boundary walk. It contains a cycle, and that cycle has length at least \(g\), by the definition of girth. Since the cycle’s length is at most the boundary-walk length, every face-boundary walk has length at least \(g\). This is the step that converts a condition on cycles into a constraint on every face.
The Planar Edge Bound from Girth
Proof. Let \(f\) be the number of faces. Count edge-face incidences by traversing face boundaries: each edge has two sides, and the total boundary length over all faces is \(2m\), including cases where an edge has the same face on both sides. Here there are no bridges, but the two-side count still gives the total. Since every face-boundary walk has length at least \(g\), summing over the \(f\) faces gives \(2m\ge gf\).
Euler’s formula for a connected plane graph is \(n-m+f=2\), so \(f=2-n+m\). Substitute this expression into the incidence inequality and rearrange: $$ 2m\ge g(2-n+m),\qquad (g-2)m\le g(n-2). $$ Because \(g\ge 3\), the factor \(g-2\) is positive. Dividing by it proves the stated bound. For equality in the bound, the rearrangement must have begun with equality \(2m=gf\). The sum of the \(f\) face-boundary lengths equals \(gf\) exactly when every one of those lengths equals \(g\). Conversely, if every face-boundary length is \(g\), then \(2m=gf\), and the same algebra gives equality in the edge bound. \(\square\)
The estimate depends on the actual girth, not just on the fact that the graph is simple. A larger girth raises the minimum length allowed for each face boundary, which leaves room for fewer edges relative to the number of vertices. The theorem applies to the specified plane graph, but its quantities \(n\), \(m\) and \(g\) are properties of the underlying graph.
Worked Example: A Plane 5-Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45,51\}\), embedded as a pentagon. It is connected and has no bridges because each edge lies on the 5-cycle. Its only cycle has length \(5\), so \(n=5\), \(m=5\), and \(g=5\).
The theorem gives $$ m\le \frac{5(5-2)}{5-2}=\frac{15}{3}=5. $$ Thus the graph meets the bound with equality. The two faces have boundary walks \(1,2,3,4,5,1\) and \(1,5,4,3,2,1\), both of length \(5\).
Check: The total face-boundary length is \(5+5=10\), while \(2m=2\cdot5=10\). Both face lengths equal \(g=5\), so the equality condition is satisfied.
Worked Example: A Plane Embedding of \(K_4\)
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,14,24,34\}\). Embed the triangle \(123\) as the outer boundary and place vertex \(4\) inside it, joined to \(1,2,3\). The graph is connected and bridgeless: each edge belongs to a triangle. Its shortest cycles are triangles, so \(n=4\), \(m=6\), and \(g=3\).
The bound is $$ m\le \frac{3(4-2)}{3-2}=\frac{6}{1}=6. $$ The three interior face-boundary walks are \(1,2,4,1\), \(2,3,4,2\), and \(3,1,4,3\), each of length \(3\). The outer face has boundary walk \(1,2,3,1\), also of length \(3\). Thus equality holds.
Check: The four boundary lengths sum to \(3+3+3+3=12\), and \(2m=2\cdot6=12\). Every face has length \(g=3\), independently confirming equality.
Worked Example: Two Squares Sharing a Vertex
Let \(G\) have \(V=\{a,b,c,d,e,f,h\}\) and \(E=\{ab,bc,cd,da,ae,ef,fh,ha\}\). Embed the cycles \(a,b,c,d,a\) and \(a,e,f,h,a\) as two squares that meet only at \(a\), with no other intersections. The graph is connected, and every edge lies on one of the two squares, so it has no bridges. There is no triangle, and the squares give cycles of length \(4\); hence \(g=4\), \(n=7\), and \(m=8\).
The theorem gives $$ m\le \frac{4(7-2)}{4-2}=\frac{20}{2}=10. $$ The actual size \(m=8\) is strictly below the bound. The two bounded faces have boundary length \(4\) each. The outer face has boundary walk \(a,b,c,d,a,h,f,e,a\), of length \(8\).
Check: The face-boundary lengths sum to \(4+4+8=16\), and \(2m=2\cdot8=16\). The outer boundary is longer than \(g=4\), so not every face has length \(g\); accordingly, equality does not hold.
Scope and a Common Mistake
The assumption that the graph has at least one edge is essential, even though it may seem automatic from “connected and bridgeless.” The one-vertex graph \(K_1\) is connected and has no bridges vacuously, but it contains no cycle, so its girth is undefined. It is excluded from the theorem. In a connected graph, having at least one edge is equivalent to having at least two vertices; under the additional bridgeless condition, the argument above then ensures that a cycle exists.
Common mistake: assigning a girth to \(K_1\). If one incorrectly assigns \(g=3\) to \(K_1\) merely because simple graphs have no cycles shorter than \(3\), the formula would give \(m\le 3(1-2)/(3-2)=-3\), although \(m=0\). The calculation is invalid because girth is the length of a shortest cycle, and \(K_1\) has no cycle. The correction is to check first that the graph contains a cycle; the theorem’s nonempty-edge and bridgeless hypotheses ensure this for connected graphs in its scope.
Another important point is that “every face boundary has length at least \(g\)” is not a rule for all plane graphs. A bridge can be traversed twice in one face boundary, and a tree has no cycles from which to define a finite girth. The bridgeless hypothesis is what lets each face boundary be treated as a closed trail, so that the lemma supplies a cycle on that boundary.
The equality condition is also more precise than saying that the graph has many shortest cycles. Equality requires every face-boundary walk to have length \(g\). The two-square example has two shortest cycles, but its outer face has boundary length \(8\), so it falls short of equality. This face-by-face test is often the most direct way to decide whether a particular plane graph attains the bound.
Check Your Understanding
Use the hypotheses and the face-counting argument to answer the following questions.
- Why does a connected bridgeless graph with at least one edge contain a cycle?
- For a connected bridgeless plane graph with \(n=6\) and girth \(g=4\), what upper bound does the theorem give for \(m\)?
- In the proof, why is the sum of all face-boundary lengths \(2m\), rather than \(m\)?
- What condition on the face-boundary walks is equivalent to equality in the planar edge bound?
- Why can the theorem not be applied to the connected graph \(K_1\)?