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?
$\endgroup$ 54 Answers
$\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$ $\begingroup$For many approaches to Euler's formula look at:
$\endgroup$ $\begingroup$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 ....
$\endgroup$ $\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$
