GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
275 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 (56.9k points) 36 193 500 | 275 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 (89.1k points) 15 58 295
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23642 Points

  2. Bikram

    17188 Points

  3. Habibkhan

    8734 Points

  4. srestha

    6404 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5098 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4478 Points

  9. sushmita

    4008 Points

  10. Rishi yadav

    3960 Points


Recent Badges

Popular Question Bikram
Regular Mr.OOPs
Avid Reader Venkat Sai
Popular Question jothee
Verified Human anchal Singh
Great Question Kathleen
Verified Human Ankita_ Pawar
Avid Reader kenzou
Notable Question Sumit Chaudhary 2
Nice Comment rahul sharma 5
27,380 questions
35,231 answers
84,395 comments
33,389 users