# Euler's formula for connected planar graphs

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?

-
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
add comment

## 2 Answers

For many approaches to Euler's formula look at:

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

-
add comment

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.

-
add comment