Proof of Euler's graph theorem: $f=e-v+2$. Is it correct and how can it be improved?

97 Views Asked by At

Definitions:

A planar graph is a connected, simple graph.

A face in a planar graph is any $2$D space that is enclosed by edges. The "background" also counts as a face.

$f$ = no. faces

$e$ = no. edges

$v$ = no. vertices


Statement:

$f=e-v+2$


First lemma:

Imagine a simple graph consisting of a string, where the end vertices have a degree of one, and the linking vertices all have a degree of two. In such a graph, $v-e = 1$. We see this is true when you start with a a segment; two vertices linked by an edge. In this case, $v-e=1$. If you add a vertex on that edge, it will split the edge into two. The number of vertices goes up by one, and the number of edges goes up by one, meaning nothing changes. This can be done with arbitrarily many vertices, meaning $v-e=1$ always holds for these kinds of graphs.

Second lemma:

The planar graph with two faces (the background + one created by the edges and vertices) is really just a string with an edge linking back to a pre-existing vertex. Since an edge is added, but a vertex is reused, $v-e=0$ in this case.

Final proof:

The above process can be reiterated. To add a face to a planar graph, a string is extended out from it. If the string ends with a pendant vertex, it does not change $\Delta(e,v)$, since the string has to be connected to the rest of the graph. Since it has to be connected, it will reuse one vertex immediately.

If, instead of ending in a pendant vertex, this string returns back to the graph and connects to a vertex, this string will have added a face to the graph. When the final edge that connects the links the string back to the graph is added, a new edge is added, but no new vertex is added, since a pre-existing one is reused. This increases the difference between the no. edges and vertices by one, corresponding to the increase in the no. faces. This can be done over and over again, and every time one vertex will be reused.