# Graph Theory Confusion

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

-
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. –  MJD Mar 18 '12 at 18:29
Probably this will be necessary en.wikipedia.org/wiki/Euler_characteristic#Planar_graphs –  Graphth Mar 18 '12 at 20:06

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

-
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. –  alex.jordan Mar 18 '12 at 23:40
@alex.jordan Surely the edges don't have to be straight lines? –  JohnJamesSmith Mar 18 '12 at 23:41
Good point! Plus 1 –  alex.jordan Mar 19 '12 at 2:31