GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
172 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 (48k points)   | 172 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 (66.5k 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 Jun 2017
  1. Bikram

    3686 Points

  2. Hemant Parihar

    1480 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1334 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1110 Points

  8. Arjun

    916 Points

  9. srestha

    898 Points

  10. Debashish Deka

    896 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1942 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. just_bhavana

    368 Points


23,347 questions
30,050 answers
67,327 comments
28,372 users