Show that if G is a disconnected graph containing exactly two odd vertices, then these odd vertices must be in the same component of G.

861 Views Asked by At

I'm currently working in the following graph theory excercise:

Show that if $G$ is a disconnected graph containing exactly two odd vertices, then these odd vertices must be in the same component of $G$.

I'm thinking about the lemma: If

$$deg(u)+deg(v) ≥ n-1$$

Then $G$ is connected and $diam(G) ≥ 2$

But haven't find a way to suit the lemma in my solution, thanks in advance for any hint or help.

1

There are 1 best solutions below

0
On BEST ANSWER

Hint:

The sum of degrees in any graph is even — in particular, this is true about each connected component of $G$.