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

Loading Question

asked in Graph Theory by Veteran (10.1k points)   | 128 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 (65.1k 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 Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2606 Points

  5. Debashish Deka

    2088 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1312 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1166 Points

  10. Sanjay Sharma

    984 Points

Monthly Topper: Rs. 500 gift card

21,438 questions
26,753 answers
60,913 comments
22,926 users