GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
185 views

Loading Question

asked in Graph Theory by Veteran (12.2k points) 9 73 139 | 185 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 (89.3k points) 15 58 296
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.8k points) 7 19 34


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

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8962 Points

  4. srestha

    6460 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4892 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4052 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Popular Question makhdoom ghaya
Great Question makhdoom ghaya
Famous Question makhdoom ghaya
Notable Question PriDix
Popular Question ManojK
Reader Chandramani Adil
Regular qwerty007
Notable Question rishu_darkshadow
Popular Question Rishi yadav
Popular Question makhdoom ghaya
27,417 questions
35,262 answers
84,532 comments
33,497 users