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.

Euler's formula for connected planar graphs (i.e. a single connected component) states that $v-e+f=2$. State the generalization of Euler's formula for planar graphs with $k$ connected components (where $k\geq1$).

The correct answer is $v-e+f=1+k$, but I'm not understanding the reasoning behind it. Anyone care to share some insight?

share|improve this question
    
Write down Euler's formula for each connected component and combine them. –  Qiaochu Yuan Nov 28 '10 at 21:15
    
Can you elaborate some more please :) –  maq Nov 28 '10 at 21:27
    
What do you have trouble understanding? –  Qiaochu Yuan Nov 28 '10 at 21:27
    
Well it's the first time I've really come across this formula. I tried doing what you said: $v-e+f=2$, and I wrote that down several times to see if I could do anything with it, but I couldnt. –  maq Nov 28 '10 at 21:29
    
Then you should try to understand Euler's formula better first. (For one thing, there is a slight subtlety in the definition of f that you should be aware of.) Try playing around with examples and/or going through a proof. –  Qiaochu Yuan Nov 28 '10 at 21:42

3 Answers 3

up vote 3 down vote accepted

For many approaches to Euler's formula look at:

http://www.ics.uci.edu/~eppstein/junkyard/euler/

share|improve this answer

The usual proof of Euler's formula works by first triangulating the graphs, then removing triangles one by one until you reach a single triangle; all these respect the Euler characteristic $v-e+f$. The proof is completed by calculating $v-e+f$ for a triangle.

You can do the same here - the first phase is the same, and in the end you will be left with $k$ triangles. Then all you have to do is calculate $v-e+f$ for $k$ unconnected triangles. Since $v=e$ for any collection of triangles, the result is the same as the number of faces, which is $1+k$: one face per triangle, and an extra outer face.

share|improve this answer

Consider 2 components...

Component 1

Component2

Both are similar components now for first excluding face f4 three faces for each component is considered so for both components V - E + (F-1) = 1 since, V = 10, E = 12 So, for adding both we get 2V - 2E + 2F-2 = 2

Now we will consider face F4 which will be unbounded face for whole graph and will we counted once so,adding 1 on both sides 2V - 2E + 2F-1 = 3 Where, total number of vertices = 2V total number of edges = 2E total number of faces = 2F-1 total number of components = k = 2

so, Vtotal - Etotal + Ftotal = k+1 can be proved. hope this helps ....

share|improve this answer

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.