# Planar graph, number of faces

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.

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

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)

-

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.

-