The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
182 views
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
asked in Graph Theory by Active (1.2k points) | 182 views

1 Answer

+2 votes
Best answer

(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

answered by Veteran (60.8k points)
selected by
0
nicely explained. Thanks :)

Related questions

+3 votes
0 answers
5
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,083 answers
187,208 comments
70,992 users