Elementary proof of Euler characteristic bound for genus $g$ surfaces. 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

*

*an open disk

*an open cylinder

*a punctured torus

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

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

*

*adds a cut to an existing face of $G - S$ (but keeps it connected), or

*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).
