Prove that if a graph G has exactly two vertices u and v of odd degree, then G has a u, v-path.

I began my proof assuming to the contrary that G does not have a u, v-path, but I'm having trouble figuring out how to show this isn't possible.

Printable View

- Jan 23rd 2011, 12:00 PMmeggnogu, v-path
Prove that if a graph G has exactly two vertices u and v of odd degree, then G has a u, v-path.

I began my proof assuming to the contrary that G does not have a u, v-path, but I'm having trouble figuring out how to show this isn't possible. - Jan 23rd 2011, 12:08 PMPlato