# 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

For many approaches to Euler's formula look at:

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

-

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.

-

Consider 2 components...

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 ....

-