edited by
1,000 views
7 votes
7 votes

Consider the following statements

$S1:2,3,3,3,3,3,4$ is a graphic sequence

$S2:$ A connected graph with $10$ vertices and $16$ edges without having a cycle of length $3$, is a planar graph.

  1. Both $S1$ and $S2$ are true
  2. $S1$ is false but $S2$ is true
  3. $S2$ is false but $S1$ is true
  4. Both $S1$ and $S2$ are false
edited by

2 Answers

Best answer
5 votes
5 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

selected by
0 votes
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

Related questions

2 votes
2 votes
2 answers
1
dan31 asked Nov 6, 2018
2,237 views
Consider the given statementsS1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G.S2:In a simple graph G, if degree of e...
2 votes
2 votes
2 answers
2
thor asked Dec 28, 2016
1,279 views