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

Loading Question

asked in Graph Theory by Boss (7.3k points)   | 123 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 (64.9k 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 Feb 2017
  1. Arjun

    5234 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3828 Points

  4. Aboveallplayer

    3006 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2148 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,841 questions
26,000 answers
59,638 comments
22,073 users