# Understanding the proof of Euler's formula

I have some difficulties in understanding the proof (written above and taken from here, pp. $$5$$-$$6$$) to the following theorem.

Theorem (Euler's formula):

If $$G$$ is a connected plane graph with $$V$$ vertices, $$E$$ edges, and $$F$$ faces, then $$V+F-E=2$$.

Proof (by induction on $$F$$):

$$G$$ is connected and has only one face. It is a tree, so $$E=V-1$$ and therefore $$V+F-E=V+1-(V-1)=2$$.

Now, suppose the formula holds for a connected graph with $$n$$ faces. We prove that it holds for $$n+1$$ faces.

Choose an edge connecting two faces of $$G$$ and remove it. The resulting graph remains connected. The new graph has one fewer edge and one fewer face. So, by the inductive hypothesis, $$V+(F-1)-(E-1)=V+F-E=2$$.

In the proof above, it's not clear to me how we can "legally" consider a graph with fewer edges and faces. I know this is how sometimes induction works, since you want to reduce it from the "$$n+1$$" to the "$$n$$" case, in order to apply the induction hypothesis. But it's just not clicking with me right now.

• I don't understand what you don't understand. Dec 18 '12 at 6:16

You ask how we can 'legally' consider a graph with fewer edges. Of course we can consider whatever we want, so I suppose you mean something like why we can consider it instead of the larger graph. In the equation $V+(F-1)-(E-1)=V+F-E=2$, the variables $V$, $F$ and $E$ are the vertex/face/edge counts of the larger graph with $n+1$ faces, and the part $V+(F-1)-(E-1)=2$ is the induction hypothesis applied to the smaller graph with the edge removed: It has $n$ faces, so by the induction hypothesis Euler's formula holds for it; since it has $V$ vertices, $F-1$ faces and $E-1$ edges, we have $V+(F-1)-(E-1)=2$. Now cancel the ones to obtain $V+F-E=2$. This is Euler's formula for the larger graph with $n+1$ faces, which is what we needed to prove to complete the induction.