Bipartite Planar Graphs and the 2V - 4 Bound

Why Bipartite Planar Graphs Have a Sharper Bound

For a simple planar graph with at least three vertices, the general edge bound is \(m\le 3n-6\). Bipartite graphs have an additional restriction: they contain no odd cycles. In a plane embedding, this forces every facial boundary walk to have even length. Combining that fact with Euler’s formula gives a sharper bound, \(m\le 2n-4\).

The face-counting argument must allow for bridges. A face boundary need not be a cycle: it can repeat vertices and edges, and the two sides of a bridge can belong to the same face. Counting boundary walks rather than assuming faces are bounded by cycles makes the argument work for these cases too.

Throughout, graphs are finite and simple. We write \(n=|V|\) and \(m=|E|\). In a connected plane graph, Euler’s formula is \(n-m+f=2\), where \(f\) is the number of faces. Also, the sum of the lengths of the facial boundary walks is \(2m\): every edge has two sides, and each side is counted once. For a bridge, both sides may border the same face, but they still contribute two to the total.

Even Facial Boundaries, Including Bridges

A bipartite graph has a partition of its vertices into two sets such that every edge joins different sets. Along any walk in the graph, the visited sets therefore alternate. If the walk is closed, it returns to its starting set, so its length is even. A facial boundary walk is closed, even when it repeats vertices or edges, so its length is even as well.

Proof. A facial boundary walk has positive length: the connected graph has at least three vertices and hence has edges, and each face is bordered by edge-sides. The walk is closed, so bipartiteness makes its length even. It remains to exclude length \(2\), since length \(0\) is not possible and a positive even length other than \(2\) is at least \(4\).

If a facial boundary walk had length \(2\), it would traverse an edge \(uv\) and immediately traverse it back. Simplicity rules out two distinct parallel edges between \(u\) and \(v\), so the same edge must be used twice. In tracing a face boundary, after arriving at a vertex the next edge is determined by the next incident edge in the cyclic order around that vertex. The walk can immediately reverse along \(uv\) only if \(u\) has degree \(1\); the same reasoning at \(v\) shows that \(v\) has degree \(1\). Since the graph is connected, it would then consist only of \(u\) and \(v\) and their edge. That contradicts the assumption of at least three vertices. Thus no facial boundary has length \(2\), and every face has boundary length at least \(4\). \(\square\)

This argument explains why bridges do not invalidate the lower bound on face lengths. They can be traversed twice along a single face boundary, but they do not create a length-\(2\) face boundary unless the entire connected graph is just one edge.

The Bipartite Planar Edge Bound

Proof. Choose a plane embedding of \(G\), and let \(f\) be its number of faces. By the lemma, each face boundary has length at least \(4\). Summing the face-boundary lengths counts both sides of every edge, even when both sides belong to the same face. Therefore

Euler’s formula gives \(f=2-n+m\). Substitute this value into the inequality and rearrange:

All the hypotheses have a role in this derivation. Connectedness permits the form \(n-m+f=2\) of Euler’s formula; simplicity and \(n\ge3\) exclude a facial boundary of length \(2\); and bipartiteness makes the facial boundary lengths even. \(\square\)

Worked Examples

Common Pitfall: Counting an Edge Only Once

A frequent error is to count each edge once when summing face-boundary lengths. In the path example, that would give a total of \(3\), the number of edges. But the actual facial boundary is \(1,2,3,4,3,2,1\), which has length \(6\). The correct total is \(2m=2\cdot3=6\), because each edge has two sides. In a graph with bridges those two sides may belong to the same face; that does not turn them into one side or one boundary traversal.

A related error is to assume that every face boundary is a cycle. The path has one face and no cycles at all, yet its face has a boundary walk of length \(6\). The proof needs only that facial boundaries are closed walks: bipartiteness makes their lengths even, and the hypotheses rule out length \(2\).

Why the Bound Is Useful

The inequality \(m\le2n-4\) is a quick necessary condition for a connected simple bipartite graph with at least three vertices to be planar. If a graph satisfying the other hypotheses has more than \(2n-4\) edges, it cannot be planar. The converse does not follow: meeting the inequality does not by itself provide a plane embedding.

The proof also illustrates a general face-counting strategy. First establish a lower bound on the length of each face boundary; then sum those lengths by counting edge-sides; finally combine the resulting inequality with Euler’s formula. For bipartite graphs, evenness strengthens the face-length bound to \(4\) once length \(2\) has been excluded. Bridges fit the same strategy because boundary lengths count traversals, not just distinct edges or vertices.