The Gateway to Computer Science Excellence

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

+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

52,315 questions

60,427 answers

201,750 comments

95,226 users