3
$\begingroup$

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?

  • 0
    Write down Euler's formula for each connected component and combine them.2010-11-28
  • 0
    Can you elaborate some more please :)2010-11-28
  • 0
    What do you have trouble understanding?2010-11-28
  • 0
    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.2010-11-28
  • 0
    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.2010-11-28

4 Answers 4

2

Given k many components you can "connect" it by adding k-1 many edges, say e'=e+(k-1). Then v-e'+f=2 just says v-e-k+1+f=2 or that v-e+f=1+k.

Note that this agrees with the regular connected version where k just equals 1.

5

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.

4

For many approaches to Euler's formula look at:

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

3

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