3
$\begingroup$

I need to determine the number of faces of a planar graph with $n$ vertices, $m$ edges and $k$ connected components. I was thinking of using Euler's formula $f=m-n+2$ but that is for a connected graph. Because I have $k$ components I was thinking $k$ times Euler formula, for each connected component.

Any advice or help is welcome.

$\endgroup$
  • 2
    $\begingroup$ My advice would be to draw a bunch of examples with, say, three connected components, and calculate $f-m+n$ for each of them, and make a conjecture, and prove it. If you get stuck along the way, come back, tell us what you've done, and someone will help. $\endgroup$ – Gerry Myerson Feb 14 '13 at 12:34
  • 3
    $\begingroup$ In the Euler's formula for a connected planar graph $f-m+n=2$, one of the face is the exterior face. If you only count the inner face, it is $f_{inner}-m+n=1$. If you have $k$ connected component, you get $f_{inner}-m+n=k$. Add back the exterior face, you get $f-m+n=k+1$. $\endgroup$ – achille hui Feb 14 '13 at 13:01
3
$\begingroup$

Euler's formula can be extended $$ V+F = E +C+\chi, $$ where $C$ is the number of components and $\chi$ is Euler's characteristic of the surface where the graph lives on. If you deal with $k$-regular planar graphs the mean face degree obeys: $$ \frac{\sum f_k}{F}=\frac {2k}{k -2} \left( 1-\frac{1+\chi}{F}\right) $$ (see here)

$\endgroup$
4
$\begingroup$

We will count the outer face as its own face. So a cycle has two faces, for example.

The idea is to take each connected component $C_1$, $C_2$, etc., and connect them by drawing a bridge between $C_1$ and $C_2$, $C_2$ and $C_3$, etc. We will thus add $n-1$ edges (the restriction is if you contract the connected components we had previously, you must form a tree).

  • $F = f$ remains the same.
  • $V = n$ since no vertices were added.
  • $E = m + k - 1$ since $k-1$ edges were added.

Now apply Euler's formula.

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