Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I don't understand what you don't understand. –  Qiaochu Yuan Dec 18 '12 at 6:16
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
That was in fact the source of my confusion, and answers my question. Thanks for the help. –  Alex Petzke Dec 18 '12 at 17:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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