Why is Euler's formula for connected planar graphs different on Toruses?

Question

I was a youtube video on Euler's formula for planar graphs. https://www.youtube.com/watch?v=VvCytJvd4H0&vl=en The creator of the video provides a very satisfying proof of why Euler's formula is V - E + F = 2 for planar graphs on a flat sheet of paper and then asks the viewers to attempt to determine why V - E + F = 0 for a planar graph on a torus. I have tried many variations of the graph of a mug (which I understand has the same topological properties as a torus) and have only been able to determine V - E + F to be equal to 1 by including the handle in my calculations. Could someone please provide me with a proof for this?

Answer 1

Euler's formula generalise to any closed orientable surface of genus $g$ (genus $\approx$ number of "handles" in your surface): $$ V-E+F=2-2g$$

Or to any closed non-orientable surface of genus $k$ $$V-E+F=2-k$$

The wikipedia article on Euler's characteristic should give you plenty enough information.

Answer 2

The best thing to do is to use an abstraction for the torus to get a better intuitive handle on things. In particular, imagine taking a square and joining its left edge to its right one by bending it backwards. You glue that edge in place - giving yourself a cylinder with an open top and bottom. Then, you stretch the cylinder and bend it to mate the top edge with the bottom edge. This gives you a torus!

We can pictorially represent this process in two dimensions: a torus is really just a square in which, whenever you hit an edge, you pop out the opposite edge that you would have glued to - so you wrap around each time you reach the edge. Try playing around with that model a bit to get a feel for how it works. Note that a few strange things can happen - like, you could draw a single point in the middle, then draw two edges connecting that point to itself: one going straight up, wrapping back to the bottom, then continuing up back to the point, and one going left and wrapping back to the right. If you count, you find $1$ vertex and $2$ edges along with $1$ face (which is a square).

You can also realize that, while the result for planes is fairly robust, the result for a torus is weaker: if I took the previous diagram and removed an edge, I'd have $1$ vertex and $1$ edge, but only $1$ "face" - except that the face would be a cylinder, which is not allowed. Basically, there is a condition: the Euler formula only works if all of the regions you have are actually polygons. This isn't an issue for connected non-empty graphs in the plane, but causes trouble for toruses.

A reasonable, if somewhat informal, proof for the torus would be to nudge your graph around in this square - without changing the number of vertices, edges, and faces - so that no vertex is on the edge of the square and no edge passes through a vertex of a square. Then, you draw, as part of a graph, the edges of the "imaginary" square you were using as your torus, adding a vertex wherever these edges intersect an edge of your original graph. This gives you a procedure that turns graphs on a torus into graphs on a plane.

Exactly proving it can be difficult without deeper mathematical ideas - you end up with trouble because the usual argument of "remove an edge and see what happens" no longer works, since doing so might merge two polygons into something that's not a polygon.

A simple, if much less than formal, intuition is that, if you want to draw a graph on a torus, you could start by putting a vertex at the corner of the square -which, in your square, will appear at every corner. Then, you draw some number $k$ of vertices on each edge - noting that these appear on both of the glued edges in your graph - and you connect these vertices along the edge of the square. Then, you draw some graph inside the square, allowing for edges to pass to the edge of the square. You view this as a planar graph with $V'$ vertices and $E'$ edges and $F'$ faces and get that $V'-E'+F'=2$.

However, if you let your graph on the torus have $V$ vertices and $E$ edges and $F$ faces, you find that $V'=V+3+k$ because the corner appears $4$ times in the plane and each of the $k$ vertices on the edge appears twice times. You find that $E'=E+2+k$ because, as there are $2k+4$ total vertices on the boundary of the square viewed in the plane, connected in a cycle, there are equally many edges. Each edge is the same as the one on the opposite side of the square when viewed on the torus, so half of these - $k+2$ - were added when we view this in the plane. Finally, $F'=F+1$ because no two faces in the square are identified, but we do add an extra face for the "exterior" which wasn't there before.

If we substitute in these formulas, we get $$(V+3+k)-(E+2+k)+(F+1)=2$$ which simplifies to $V-E+F=0$.

The part of the proof that is missing is that this only covers the case where we include the boundary of the imaginary square inside of the graph itself - a true proof would need to start from an arbitrary graph and show it from there. A quick fix to this issue is to start with an arbitrary graph and then add edges and vertices - making sure not to modify the quantity $V-E+F$ in doing so - until you get to a case where this proof applies.