[Math] Planar graph, number of faces

graph theoryplanar-graphs

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.

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

Related Question