148 views

• How many planar regions?
• How many closed regions? and how many are unbounded?
• How many of then are bounded by a cycle of length $4$ ?
• Now, for example (a different question, not related to above diagram ) a question says, In a connected 3 regular graph, every planar region is bounded by exactly 5 edges, then count no of edges?

Please explain the last QS with the help of Euler's equation.

+1 vote

A) As the given graph is a planar graph and secondly we have only one connected component , so we can find the number of regions of the graph as  :

r   =   e - n + 2

==> r   =   12 - 9 + 2

==> r   =   5

Out of these 4 will be closed regions and 1 as unbounded region..

Now as clear from the graph , all of 4 closed regions are cycles of 4 edges..

Now coming to your last question,

Say number of regions are "r" , then

No of edges which bound the region =  5r

But to remove double counting , we do no of edges  =  5r / 2

Also say we have n vertices ,and the graph is 3 regular , so sum of degree  = 3n which is also = 2e  =  5r  according to Handshaking Theorem..

So as the graph is planar so we have :

r = e - n + 2

==> 3n / 5  =  (3n / 2) - n + 2

==>  (3n / 5) - (n / 2)   =   2

==>  n  =  20 vertices

So no of edges = 3n/2  =  30 edges

r = total regions right ? that includes unbounded one also ??
Think it this way :

"Every planar region is bounded by 5 edges"..So when we assume r regions we have to see in totality..Here it is not said "every closed planar region" ..In that case the answer will differ..

That is not my QS.

• We use $r = e - n +2$ equation. Here r = total regions. You agree with that. Fine !
• $e = \frac{5r}{2}$ , what is that $r$ ? closed or, bounded ? or total ?
Total in the given context

"No of edges which bound the region =  5r" now explain this statement. I am not getting. Could you please construct a small planar graph like above, and explain. (not large, otherwise it would be time waste)

Forget about regularity for time being. Or mention need of regularity in this QS context. (if there is any implicit meaning of regularity in such graph)

Just for sake of simplicity , take a triangle..Simplest example possible..:)..

Here if we find no of edges as I found above then , if we take r = 2 , then e = 3r / 2 ==> 3* 2 / 2 = 3 and we get we get correct result ..

Also for triangle ,

2n = 2e [As degree is 2] ==> n = e = 3..

Hence our approach is fine as is evident from this small example..

So in our original solution , in the term 5r / 2  which is no of edges, the 'r' is referred to total number of regions..

yes..correct for n = 3 , triangle I have tested. Formula working thats good but.

These lines. "how unbounded region will be bounded by 5 edges and that unbounded region will contribute to edge counting so that we need to divide 5r by 2..etc..".. things not clear.

Any way, your solution method , I have seen many places, and seen accepted as well. it's OK !
Ya your doubt is also genuine..I am also not able to digest this thing..:)..But this is done mathematically
degree of a region is the number of boundary edges touching a region.

And In a simple connected planar graph with minimum degree of a region $k$.

e <= k(V-2)/(k-2) and $kr <= 2e$

And in graph in question, $k = 4$

Say number of regions are "r" , then

No of edges which bound the region =  5r

1
+1 vote
2
+1 vote