# Question on proof of Euler's formula

For some reason I'm having a difficult time understanding the proof of Euler's formula. I'm fine right up until the end.

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

Proof (proceeding 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, and 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 edges and one fewer faces. So by the inductive hypothesis, $V+(F-1)-(E-1)=V+F-E=2$.

This will probably be one of those 'oh, duh' things, but I just don't see how we can 'legally' consider a graph with fewer edges and faces. I know this is how induction works sometimes, 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. Help is much appreciated. Thanks.

Proof obtained from these notes.

-
I don't understand what you don't understand. – Qiaochu Yuan 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.