1
$\begingroup$

What is the most number of regions (including the outside region) can a planar graph with V vertexes partition split the plane into? (No self-loops or multiedges allowed)

Im stumped on this question i know outside is 1

  • 0
    Probably this will be necessary http://en.wikipedia.org/wiki/Euler_characteristic#Planar_graphs2012-03-18

1 Answers 1

4

Let $F$, $E$, $V$ be the number of faces, edges, and vertices, respectively. If some face has more than three sides that we can just make more faces by connecting non-adjacent vertices of that face. So we want every face to be a triangle. Therefore $E = 3F/2$. Plug this into $F-E+V=2$ and we get $\boxed{F = 2V-4}$ for $V\geq 3$.

  • 0
    Good point! Plus 12012-03-19