1,432 views
0 votes
0 votes
Consider following statements: 
(i) Every simple graph has at least two vertices of the same degree. 
(ii) If u is a vertex of odd degree in a graph, then there exists a 
path from u to another vertex v of the graph where v also has odd degree. 
(iii) If there are exactly two vertices a and b of odd degree, 
there is an Eulerian cycle in the graph. Which of the above statements are not true? 
(A) (i) and (ii) only 
(B) (iii) only 
(C) (ii) only 
(D) None of the above

1 Answer

Best answer
2 votes
2 votes

(i) Every simple graph has at least two vertices of the same degree.  --- TRUE

 

proof by contradiction:- 

Every simple graph has none of the vertices of the same degree.

let there are n vertices, in a simple graph maximum degree of a vertex = n-1.

therefore according to the statement, the degree sequence must be 0,1,2,3,.....,(n-1)

is this sequence is valid? 

No, due to one vertex degree=0 ===> Maximum degree can exist = n-2, but in our sequence, a vertex with degree = n-1 is exist.

Therefore your assumption is wrong.

 

(ii) If u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree.  ---- TRUE

if you take connected graph, then it is trivial. ( i mean there exist a path every pair of vertices ), Take a disconnected graph ( therefore it have more than one component. )

Let take it have 2 components, first component have x vertices, second component have y vertices.

we know that every graph has even no.of odd degree vertices.

think each component is separate graph, therefore if the first (second) component have a vertex odd degree (let u), then it must have another vertex(let v) which is odd degree ===> x is a component therefore u and v should be connected, connected means there is a path between u and v

 

(iii) If there are exactly two vertices a and b of odd degree, there is an Eulerian cycle in the graph --- False

we all know that, A graph have Eulerian cycle iff every vertex has even degree

 

the correct statement is:-

If there are exactly two vertices a and b of odd degree, there is an Eulerian path in the graph

selected by

Related questions

2 votes
2 votes
1 answer
4