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.