Surface Edge Bounds and Genus Lower Bounds

Why Edge Counts Restrict Surface Genus

Euler’s formula links the vertices, edges and faces of a cellular embedding. A simple graph cannot use arbitrarily many edges on a fixed surface: each face must have enough boundary length, while the total boundary length is exactly twice the number of edges. Combining these facts gives an upper bound on the size of an embedded graph. Rearranging that bound gives a necessary lower bound on the genus of a surface that can contain the graph.

Throughout, graphs are finite and simple. An embedding is cellular when every component of the complement of the embedded graph is an open disk; those components are its faces. The surface is closed and connected. We consider connected graphs with \(n=|V(G)|\ge3\), and write \(m=|E(G)|\). These hypotheses matter: for example, the edge bound below is not valid for every graph of order one or two.

For a connected cellular embedding, Euler’s formula is \(n-m+f=\chi\), where \(f\) is the number of faces and \(\chi\) is the Euler characteristic of the surface. We will also count the lengths of facial boundary walks. A boundary walk may repeat vertices or edges, so an edge used twice on the boundary is counted twice. Each edge has two sides, and each side belongs to a face; consequently, the sum of all face-boundary lengths is \(2m\).

The Surface Edge Bounds

Proof. First, every face-boundary walk has length at least \(3\). A length-one boundary walk would require a loop, which a simple graph does not have. A length-two boundary walk would have to traverse the same edge in both directions, since there are no parallel edges. In tracing a face boundary, reversing immediately along that edge at either endpoint is possible only when that endpoint has degree one: the next edge-side in the local cyclic order must otherwise be a different edge-side. Thus both endpoints would have degree one. Because the graph is connected, it would then be the graph consisting of just that one edge, contrary to \(n\ge3\). Therefore, if \(f\) is the number of faces, summing boundary lengths gives \(3f\le2m\).

On the orientable surface, Euler’s formula gives \(f=2-2g-n+m\). Substituting this expression into \(3f\le2m\) yields \(3(2-2g-n+m)\le2m\). Expanding and subtracting \(2m\) gives \(6-6g-3n+m\le0\), hence \(m\le3n-6+6g\).

On the nonorientable surface, Euler’s formula gives \(f=2-k-n+m\). Thus \(3(2-k-n+m)\le2m\), or \(6-3k-3n+m\le0\). Rearranging gives \(m\le3n-6+3k\). This proves both bounds. \(\square\)

The coefficients differ because the Euler characteristics differ: increasing orientable genus by one reduces the Euler characteristic by two, whereas increasing nonorientable genus by one reduces it by one. The inequality is a necessary condition for a cellular embedding, not a guarantee that an embedding exists when the inequality holds.

Rearranging the Bounds

Proof. The orientable edge bound \(m\le3n-6+6g\) implies \(m-3n+6\le6g\), and division by \(6>0\) gives \((m-3n+6)/6\le g\). Since \(g\) is an integer, \(g\ge\lceil(m-3n+6)/6\rceil\); also \(g\ge0\) by definition. Combining these two requirements gives the stated maximum. For the nonorientable case, \(m\le3n-6+3k\) gives \((m-3n+6)/3\le k\). The integer \(k\) is at least the ceiling of the left-hand side and, by definition of nonorientable genus, at least \(1\). This gives the second maximum. \(\square\)

These formulas are lower bounds: they can rule out a surface of too small a genus, but they need not identify the exact genus. For graph genus, one uses the standard cellularization result that a minimum orientable-genus embedding can be taken cellular; the corresponding minimum nonorientable-genus embedding is cellular for a nonplanar graph. A planar graph has nonorientable genus \(1\) under the convention above, and the nonorientable lower bound is then at most \(1\), since the planar edge bound gives \(m\le3n-6\). Thus the inequalities also give the stated genus lower bounds under these standard minimum-embedding facts.

Common Pitfalls and How to Use the Bounds

Do not omit the hypotheses. The face-length argument depends on simplicity, connectedness, cellularity and \(n\ge3\). For instance, the connected simple graph with vertices \(\{1,2\}\) and the single edge \(12\) has \(n=2,m=1\). Substituting into the planar expression \(3n-6\) gives \(0\), so the claimed inequality \(m\le3n-6\) would fail. This does not contradict the theorem: its order hypothesis is not satisfied.

Count boundary occurrences, not just distinct edges on a face. In a cellular embedding, a bridge can appear twice in the same facial boundary walk. The total over all face boundaries is \(2m\), not \(m\); that is why the proof uses \(3f\le2m\). Counting each edge only once in that step would give the wrong inequality.

Do not confuse an obstruction with a construction. If a graph satisfies \(m\le3n-6+6g\), the orientable edge bound has not proved that it embeds on genus \(g\). The bound only says that this particular edge-count obstruction does not exclude such an embedding. Other structural restrictions may still prevent it.

For a quick estimate, compute \(m-3n+6\) once. If it is positive, divide by \(6\) for the orientable lower bound and by \(3\) for the nonorientable lower bound, then round each result upward because genus is integral. If it is nonpositive, the edge count alone yields no positive orientable-genus bound; the nonorientable genus remains at least \(1\) by definition.