GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
190 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.  

asked in Graph Theory by Veteran (50.9k points)   | 190 views

1 Answer

+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 

answered by Veteran (68.7k points)  
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..

Hope this clears your doubt..
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$
Please explain ::::

Say number of regions are "r" , then

No of edges which bound the region =  5r


Top Users Aug 2017
  1. ABKUNDAN

    4654 Points

  2. Bikram

    4012 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2832 Points

  5. manu00x

    2644 Points

  6. makhdoom ghaya

    2370 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1742 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1554 Points


24,864 questions
31,941 answers
74,060 comments
30,062 users