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?

$\endgroup$
  • $\begingroup$ Write down Euler's formula for each connected component and combine them. $\endgroup$ – Qiaochu Yuan Nov 28 '10 at 21:15
  • $\begingroup$ Can you elaborate some more please :) $\endgroup$ – Snowman Nov 28 '10 at 21:27
  • $\begingroup$ What do you have trouble understanding? $\endgroup$ – Qiaochu Yuan Nov 28 '10 at 21:27
  • $\begingroup$ 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. $\endgroup$ – Snowman Nov 28 '10 at 21:29
  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Nov 28 '10 at 21:42
4
$\begingroup$

For many approaches to Euler's formula look at:

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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