Elementary proof of Euler characteristic bound for genus $g$ surfaces.

Question

In the notes for my course on Graph Theory, there is a short elementary proof of the Euler characteristic formula $V-E+F=2$ for planar graphs: see page 27 here.

In the generalisation of this formula to surfaces of genus $g \ge 1$ (i.e many-holed toruses), namely

$$V-E+F \ge 2-2g$$

the proof is left as an exercise.

I can't see how to generalise the inductive argument for the plane to genus $g \ge 1$ surfaces. Intuitively, it seems only possible for the faces of the graph to be homeomorphic to

1. an open disk
2. an open cylinder
3. a punctured torus

though proving this seems non-obvious. Is there an elementary proof of this inequality as there is for the plane?

Answer 1

We can begin by starting with an empty graph (with $n$ vertices and no edges) embedded in a genus-$g$ surface. This has only one face: a face homeomorphic to a genus-$g$ surface punctured $n$ times.

In general, we can prove by induction that as we add edges to this embedding, each face will be homeomorphic to a genus-$a$ surface punctured $b$ times, for some $(a,b)$ with $a\ge 0$ and $b\ge 1$. For short, let's call such a surface an $(a,b)$-surface. At the beginning, every "puncture" corresponds only to a vertex of the graph, but in general, it could be something more complicated.

To verify that this is all we get, we have to think about what happens when we add an edge inside a face. Under the homeomorphism to an $(a,b)$-surface, this corresponds to cutting along a curve that starts and ends at a puncture point. There are $3$ cases:

1. The curve starts and ends at different puncture points. In that case, the face remains a single face, but the $(a,b)$-surface with the curve deleted is now homeomorphic to an $(a,b-1)$-surface: we can combine the two puncture points into one.
2. The curve is a loop that starts and ends at the same puncture point, but there is at least one handle joining the interior and exterior of the loop. This is homeomorphic to a situation where the curve is a loop that cuts a handle in half. The puncture point and handle turn into two puncture points, giving us an $(a-1,b+1)$-surface.
3. The curve is a loop that starts and ends at the same puncture point, and there are no such handles. Then we get two faces. Both of them keep the puncture point corresponding to this boundary between them, and all handles and other puncture points are split between them: we get an $(a',b')$-surface and an $(a'',b'')$-surface with $a'+a''=a$ and $b'+b''=b+1$.

Now we can prove a theorem analogous to Euler's formula. To each face homeomorphic to an $(a,b)$-surface, we assign the value $2-2a-b$. Let $S$ be the sum of the values assigned to all faces. Then each of the cases above increases $S$ by $1$ (that's why the awkward value $2-2a-b$ is chosen, so the quantity $V-E+S$ doesn't change).

In the empty graph, we have $$ V - E + S = n - 0 + (2-2g-n) = 2-2g. $$ Therefore we have $V-E+S = 2-2g$ for every graph embedded in the genus-$g$ surface.

We have $S \le F$, because a $(0,1)$-surface (an open disk, or punctured sphere) is the only one with value $1$, and all other $(a,b)$-surfaces get nonpositive values. This gives us the inequality $V-E+F \ge 2-2g$.

Often, we only consider cellular embeddings, in which all faces are open disks. In this case, equality holds: $V-E+F=2-2g$. This is easier to prove, because we don't have to mess about with different types of faces (but you need a trickier base case).

Answer 2

Let $S$ be a surface that's either $S^2$ or $\Sigma_g$ (a $g$-holed torus), and $G$ a graph on $S$.

Then each component of $S - G$ (equivalently, a face of $G$) is homeomorphic to $S^2$ or $\Sigma_g$, possibly with some number of punctures: see here for a proof.

Now adding an edge to $G$ adds a cut to one of the faces of $G-S$. This means that adding an edge either

1. adds a cut to an existing face of $G - S$ (but keeps it connected), or
2. splits a face $\Sigma$ into two faces $\Sigma_1$, $\Sigma_2$, such that $\Sigma = \Sigma_1 \# \Sigma_2$, where $\#$ denotes connect sum

by the classification theorem.

Now the key idea is that we can understand 1) and 2) as constructive rather than destructive operations on faces.

For 1), it suffices to understand given a surface $\Sigma$ with at least one puncture, how to produce a surface that removes at least one such puncture. For 2), it suffices to understand given some $\Sigma$, what the possible decompositions $\Sigma_1 \# \Sigma_2$ of it are.

In case 1), either a puncture will be closed, or two will be joined. It is not possible to join at least three punctures, since the resulting object would not be a surface (something locally homeomorphic to $\mathbb{R}^2$). Joining two punctures is the same thing as adding a handle to the surface. In case 2), suppose $\Sigma_i$ has $p_i$ punctures and genus $g_i$. Then $\Sigma$ must have $p_1+p_2-1$ punctures and genus $g_1+g_2$.

It now suffices to verify that under all such operations $V-E+F \ge 2-2g$ is retained (omitted).