Path between vertices with an odd degree

156 Views Asked by At

Is it true that in an undirected graph with exactly $2$ vertices with an odd degree there is a path that connects them and why?

It must be true but I cannot prove it.

2

There are 2 best solutions below

0
On

Suppose there is no such path. Then the graph is not connected. Let $A$ and $B$ be connected components, $A$ with first vertex and $B$ with second. Then in each component we have, by Handshake lemma, at least two vertices with odd degree. So in total at least 4 vertices with odd degree. A contradiction.

1
On

graph

this is true as you can see in the above picture of graph. This is the only case of 2 vertices of odd degree so they must be connected.