Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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 – Graphth Mar 18 '12 at 20:06
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|cite|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


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.