0
$\begingroup$

Suppose there is a connected planar simple graph G with v vertices such that all its regions are triangles (a cycle consisting of three edges).

How many regions would this planar graph, G, split the plane into?


The graph we are looking at probably looks like a triangular structure that gets more complex as the number of vertices and edges increase, something like this:

enter image description here

I assume the answer will invovle this equation:

r = e - v + 2

Since I am asked to derive the number of regions (r) with only just the number of vertices (v), I must first use v to find the number of edges (e) in order to finally calculate r.

The problem is I don't know how to use v to find e.

I'm sitting on this equation:

e <= 3v - 6

It kind of suggests a connection between e and v, but the relationship is not certain. Am I suppose to use combinotirial math to find the answer?

Any feedback would be appreciated, thanks!

$\endgroup$
  • 1
    $\begingroup$ Hint: A triangle has 3 vertices and 3 edges. How many edges must you add when you add an extra vertex (remember that all of the regions have to be triangles)? Note that your graph doesn't satisfy this: the outer region has 15 edges. $\endgroup$ – user3482749 Nov 29 '18 at 16:31
  • $\begingroup$ Oh I see, if I want to make a new triangle, I put 1 vertex within the existing triangle and extend 3 edges to each of the the outer vertices, which creates three triangles within the first triangle. (This assignment has a lot of word salads.) $\endgroup$ – potatoguy Nov 29 '18 at 16:36
  • 1
    $\begingroup$ Yes. That gives you a formula for the number of edges in terms of the number of vertices, and you can use your formula to get the number of regions out of that. Alternatively, you can do it directly: the first three vertices split the plane into two regions. Each subsequent one adds two more regions. $\endgroup$ – user3482749 Nov 29 '18 at 16:38
0
$\begingroup$

Let $F$ denote the number of faces and $E$ denote the number of edges, then $F=(n-2)*2$.

Or $E=(n-2)*3$ and since $F*3=\sum_{f \in face(G)}{len(f)=2*E}=2(n-2)*3 \Rightarrow F=2*(n-2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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