edited by
1,196 views
3 votes
3 votes

How to PROVE S2 is correct??

Consider the statements 

   $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree

   $S_2$ ) A graph with $13$ vertices, $31$ edges, $3$ vertices of degree $5$ and $7$ vertices of degree $4$  does not exist.

Q) Which of the following is true?

A). $S_1$ and $S_2$ are true

B). $S_1$ is true and $S_2$ is false

C). $S_1$ is false and $S_2$ is true

D). Both $S_1$ and $S_2$ are true

edited by

3 Answers

5 votes
5 votes
s1 is true

2 vertices have same degree(use pigeonhole princliple)

for s2 apply handshaking theorem

let x be degree of no of vertices

15+28+3x=62

x=19/3

this is not poosible

x being degree need to be whole no

so d is ans

x=
0 votes
0 votes

S2 is wrong....

 as there will be even number of vertices of odd degree in any graph..  there are 3 vertices of degree 5 , so number of vertices which is 3 is wrong.. it should be even as per theorem..    since one statement is wrong , the whole statement S2 is wrong..

Related questions

0 votes
0 votes
1 answer
2
Overflow04 asked Jun 29, 2022
614 views
Someone please solve it.
2 votes
2 votes
0 answers
4