Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite
1

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

share|improve this question
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. – 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

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.