Cellular Embeddings and Euler’s Formula on Surfaces

Embeddings, Faces, and Cells

A graph drawing on a surface divides the surface into regions. On the sphere, for example, a cycle separates two regions; on the torus, a drawing can wrap around the handle and produce a different pattern of regions. To use this division in a count, it matters not only how many regions there are but also what kind they are. The key condition is that every region be an open disk.

Throughout, graphs are finite and simple, and the surfaces are compact, connected, and without boundary. An embedding of a graph $G=(V,E)$ in a surface $S$ places distinct vertices at distinct points and represents each edge by an arc joining its endpoints, with edge interiors disjoint from one another and from all vertices. A face is a connected component of $S$ after the embedded graph is removed. Write $F$ for the number of faces.

Definition: An embedding is cellular if every face is homeomorphic to an open disk. A connected cellular embedding on a closed surface gives a cell decomposition of the surface: vertices are 0-cells, edge interiors are 1-cells, and faces are 2-cells. The boundary of a face need not be a simple cycle; its boundary walk may revisit vertices or edges.

The last point is important. A face is a component of the complement, not merely a region whose boundary must be a simple polygon. In a cell decomposition, the boundary of a 2-cell can be attached to the graph in a way that identifies different points of its boundary. The open face itself is still an open disk.

Euler’s Formula for a Cellular Embedding

For a compact surface $S$, its Euler characteristic $\chi(S)$ is an invariant of the surface. The cell-decomposition formula for Euler characteristic, covered in the earlier material on compact surfaces, says that for a finite cell decomposition, $\chi(S)$ is the number of 0-cells minus the number of 1-cells plus the number of 2-cells. A cellularly embedded graph supplies exactly these three kinds of cells.

Theorem (Euler’s formula for cellular embeddings): If a finite connected graph $G$ is cellularly embedded in a compact, connected surface $S$ without boundary, then $$ |V(G)|-|E(G)|+F=\chi(S). $$

Proof. Assume $G$ is connected and its embedding in $S$ is cellular. By the definition of cellular embedding, the vertices, edge interiors, and faces form the 0-cells, 1-cells, and 2-cells of a finite cell decomposition of $S$. There are $|V(G)|$ cells of dimension 0, $|E(G)|$ of dimension 1, and $F$ of dimension 2. Applying the cell-decomposition formula for Euler characteristic gives $\chi(S)=|V(G)|-|E(G)|+F$, as required. $\square$

The formula counts cells, not geometric lengths or areas. The same surface invariant must result no matter how many vertices and edges a particular cellular drawing uses. For example, the sphere has Euler characteristic $2$, while the torus has Euler characteristic $0$. In each cellular example below, the graph and face counts recover the appropriate value.

Worked Example: The Tetrahedral Graph on the Sphere

Take $G=K_4$ with $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,13,14,23,24,34\}$. Embed it as the edges and vertices of a tetrahedron on the sphere. Its four faces have boundary cycles $123$, $124$, $134$, and $234$.

There are $4$ vertices, $6$ edges, and $4$ faces. Substituting these counts gives $$ |V(G)|-|E(G)|+F=4-6+4=2. $$ This equals the sphere’s Euler characteristic.

Check: The face boundaries contain $4\cdot3=12$ edge appearances in total. Each of the six edges lies on two face boundaries, giving $6\cdot2=12$ appearances independently. The listed faces account for every edge on both sides, consistent with the tetrahedral cell decomposition.

Worked Example: A Cycle on the Sphere

Let $G$ have $V(G)=\{0,1,2,3,4\}$ and $E(G)=\{01,12,23,34,40\}$. Draw this cycle as a simple closed curve on the sphere. The two components of its complement are open disks, so the embedding is cellular, with $F=2$.

Here $|V(G)|=5$ and $|E(G)|=5$. Thus $$ |V(G)|-|E(G)|+F=5-5+2=2, $$ which again agrees with $\chi(S)=2$.

Check: Each of the two faces has boundary length $5$, so the total number of edge appearances around face boundaries is $2\cdot5=10$. Each of the five edges borders both faces and is counted twice, giving $5\cdot2=10$.

A Cellular Embedding on the Torus

To make the torus example precise, form the torus by identifying points in the plane that differ by a vector in $3\mathbb{Z}\times3\mathbb{Z}$. Begin with the square grid in the plane and keep the vertices $(i,j)$ with $i,j\in\{0,1,2\}$, taking coordinates modulo $3$. The grid edges and square faces then descend to a drawing on the torus.

Worked Example: The Three-by-Three Grid on the Torus

Define $G$ by $$ V(G)=\{(i,j):i,j\in\{0,1,2\}\} $$ and let its edges be all unordered pairs $$ \{(i,j),(i+1\bmod 3,j)\},\qquad \{(i,j),(i,j+1\bmod 3)\}, $$ for $i,j\in\{0,1,2\}$. The modulo $3$ is part of the definition: for example, an edge from $(2,j)$ joins $(2,j)$ to $(0,j)$.

There are $3\cdot3=9$ vertices. The horizontal edges form three 3-cycles, one in each row, giving $3\cdot3=9$ horizontal edges. The vertical edges form three 3-cycles, one in each column, giving another $9$. These are distinct horizontal and vertical edges, so $|E(G)|=18$.

For each $(i,j)$, the square with corners $(i,j)$, $(i+1\bmod3,j)$, $(i+1\bmod3,j+1\bmod3)$, and $(i,j+1\bmod3)$ gives one face. There are $3\cdot3=9$ such squares. Each face interior is an open square in the plane grid and maps injectively to the torus, so these are disk faces and the embedding is cellular. Therefore $$ |V(G)|-|E(G)|+F=9-18+9=0, $$ equal to the torus’s Euler characteristic.

Check: Every vertex has four neighbors, two in its row and two in its column. The degree sum is $9\cdot4=36$, so the handshake count gives $36/2=18$ edges. Also, the nine square faces have $9\cdot4=36$ edge appearances in total; each edge borders two square faces, giving $18\cdot2=36$. Both counts agree with the construction.

Why the Cellular Condition Matters

The face count in Euler’s formula is the number of complementary components, but that count has the required meaning only under the theorem’s hypotheses. In a cellular embedding, each component is an open disk and contributes one 2-cell. If a complementary component is not a disk, simply counting it as one face does not give a cell decomposition of the surface with one 2-cell per component.

Worked Example: An Embedding That Is Not Cellular

Embed the graph with $V(G)=\{v\}$ and $E(G)=\varnothing$ in the torus by placing $v$ at one point. The complement is the torus with one point removed. It is connected, so there is $F=1$ complementary component, but this component is not an open disk: the handle of the torus remains.

The counts give $|V(G)|-|E(G)|+F=1-0+1=2$, whereas $\chi(S)=0$ for the torus. This does not contradict Euler’s formula, because the embedding is not cellular. The complementary component cannot be counted as a single 2-cell in a cell decomposition of the torus.

Common pitfall: It is incorrect to apply $V-E+F=\chi(S)$ to an arbitrary drawing merely because its complement has a finite number of components. In the example above, the tempting calculation is $1-0+1=2$; the correction is to check whether each complementary component is an open disk. Since the punctured torus is not a disk, the cellular-embedding theorem does not apply.

When using the formula, check the conditions in order: the graph is connected, the surface is compact and has no boundary, and every face is an open disk. Then count vertices, edges, and faces as cells and compare the result with the Euler characteristic of the surface. The formula links a graph drawing to the topology of its surface, while the cellular condition ensures that the link is valid.

Check Your Understanding

For each question, state which counts or hypotheses you use.

A connected graph is cellularly embedded on the sphere with $8$ vertices and $12$ edges. How many faces does it have?
Explain why a face boundary need not be a simple cycle even though the face in a cellular embedding is homeomorphic to an open disk.
For the torus grid above, verify the Euler count using its numbers of vertices, edges, and faces.
A graph embedded on a surface has three complementary components, one of which is not an open disk. May Euler’s formula for cellular embeddings be applied? Explain.
Why does the single-vertex embedding on the torus fail the cellularity condition, even though its complement has only one component?