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

Loading Question

asked in Graph Theory by Loyal (4.5k points)   | 101 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 (59.6k 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.3k points)  
Top Users Jan 2017
  1. Debashish Deka

    8322 Points

  2. sudsho

    5166 Points

  3. Habibkhan

    4718 Points

  4. Vijay Thakur

    4468 Points

  5. Bikram

    4420 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4082 Points

  8. santhoshdevulapally

    3732 Points

  9. Sushant Gokhale

    3518 Points

  10. GateSet

    3336 Points

Monthly Topper: Rs. 500 gift card

19,159 questions
24,065 answers
52,873 comments
20,288 users