(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