GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
137 views

Loading Question

asked in Graph Theory by Veteran (10.2k points)   | 137 views
Is there any formula to solve if questions asks a planar graph without cycle of length 4 or 5 or any n.????

2 Answers

+3 votes

For S1:

Following the result that the number of vertices having odd degree in the degree sequence must be even to be a valid graphic sequence.But here we have 5 vertices having degree 3 i.e. odd degree ,hence the given sequence is not a graphic sequence.Hence S1 is false.

For S2:

Given that we have not a cycle of length 3.So minimum length cycle that we can have = 4.

Let there are r such cycles (or regions) .

every region is bounded by 4 edges at least

So in r regions we have e >= 4r/2 [ We have divided by 2 to avoid double counting of edges]

                             ⇒    e >= 2r

Now we are given that the graph is planar and connected,so Euler's theorem holds.So by Euler's theorem,

                            r = e - n + 2

Substituting in the earlier result we have ,

        e >= 2(e - n + 2)

 ⇒    e  <= 2n - 4

So we have n = 10 and e = 16 which on substitution on the above inequality gives :

       16  <= 16 which is true.

Hence S2 is true.

 

Hence , option B) is true

answered by Veteran (66.2k points)  
Thanks a lot sir.
@habibkhan statement 2 is false.. e<=2n-4 is a corollary and it cant be used to prove graph is a planar..we can use it in contradiction manner if some graph doesnot satisfy the condition then it is surely non planar but if satisfies the condition we cant say anything about planarity..

example is peterson graph here e=15 and n=10 and applying corollary we get 15<=16 but we know peterson graph is non planar
0 votes
because in simple planar  graph if no of edges atleast two

the degree of every faces  will be atleast 3

because given no cycle with length 3 then the degree of every face  will be atleast 4

as we know  sum of the degree of the faces =2e

so here 4f<=2e

f<=e/2

 we use euler's theorem  v-e+f=2 to satisfy graph is planar or not

v-e+(e/2)>=2

given v=10,e=16

10-16+8>=2

2>=2

so it is planar graph
answered by Boss (9.4k points)  


Top Users May 2017
  1. Prashant.

    130 Points

  2. akankshadewangan24

    102 Points

  3. Tesla!

    90 Points

  4. Vishal Goel

    20 Points

  5. sh!va

    20 Points

  6. Arjun

    14 Points

  7. Krunal2016

    12 Points

  8. Raushank2

    10 Points

  9. Habibkhan

    10 Points

  10. akash.dinkar12

    10 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 01 - 07
  1. Prashant.

    130 Points

  2. akankshadewangan24

    102 Points

  3. Tesla!

    90 Points

  4. Vishal Goel

    20 Points

  5. sh!va

    20 Points


22,195 questions
28,249 answers
63,695 comments
24,385 users