THE GATEBOOK

Normalization Lectures

A graph contains exactly 2 odd degree vertices, x,y. Which one of the following statements is always true?

(A). There is a path from x to some even degree vertex which goes through y (B). There is a path from x to y (C). There is a path from some even degree vertex to some even degree vertex (D). There is a path from some even degree vertex to either x or y

Think of a 2 component disconnected graph...

say 1st component is consisting of only 1 vertex with degree 0

and 2nd component has to have 2 odd degree (since a single component cant have odd no. of odd degrees) therefroe there is always a path between them ie x and y but not with the other component having degree 0

therefore option B