Is it true that a finite graph having exactly two vertices of odd degree must contain a path from one to the other? Give a proof or a counterexample.

Question

kinggeorge · Answer

This is definitely true, but I'm not immediately sure on how to prove it.

anonymous · Answer

I'm starting with if I have two vertices, and I must have two vertices of odd degree than there must be a path (in the form of a single edge) from one v1 to v2. If I have 3 vertices, and exactly 2 must have an odd degree, then one must have an even degree. I don't know where I'm going yet.

kinggeorge · Answer

I suppose what we could do, is suppose BWOC that there is some graph G what is disconnected in such a way so that it has two distinct components $G_1$ and $G_2$, and each component has a single vertex of odd degree. Now let's look at $G_1$ as a subgraph of $G$.

It has a single vertex of odd degree, and some number vertices of even degree. This means that the sum of all the degrees is odd. However, this is a contradiction! Therefore, $G_1$ and $G_2$ must be connected, so there is a path between the vertices of odd degree.

anonymous · Answer

Again, thank you. I believe the proof you have provided is clear and concise. Your help has exceeded my expectations.

kinggeorge · Answer

You're very welcome :)