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
  • 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$ Commented Feb 14, 2013 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$ Commented Feb 14, 2013 at 13:01

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .