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.

  • 2
    $\begingroup$ I don't understand what you don't understand. $\endgroup$ Dec 18 '12 at 6:16

I'm also not sure what it is you don't understand; I'll try to explain the only thing I can see that might be confusing.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.