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.
Follow Math Help Forum on Facebook and Google+
Originally Posted by meggnog Prove that if a graph G has exactly two vertices u and v of odd degree, then G has a u, v-path. Do you know that a component of a graph is a maximally connected subgraph? Is it possible for the two odd vertices to be in different components?
View Tag Cloud