2
$\begingroup$

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
    I don't understand what you don't understand.2012-12-18

1 Answers 1

2

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.