GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
118 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 (41.3k points)   | 118 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 (65k 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 Feb 2017
  1. Arjun

    5386 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,021 answers
59,689 comments
22,131 users