Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Gerry Myerson Feb 14 '13 at 12:34
2  
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$. –  achille hui Feb 14 '13 at 13:01

2 Answers 2

up vote 3 down vote accepted

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)

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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