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

  • 2
    Try drawing some pictures. Start with 3 vertices and draw in as many edges as you can and see how many regions you have divided the plane into. Then try 4 vertices, then 5. Perhaps a pattern will emerge.2012-03-18
  • 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
    This assumes noncolinear vertices and convex faces. It also doesn't tell us what to do with the exterior face. This is the right answer, but there are some details to hash out.2012-03-18
  • 0
    @alex.jordan Surely the edges don't have to be straight lines?2012-03-18
  • 0
    Good point! Plus 12012-03-19