How would you prove that for a connected graph with an even number of vertices and an odd number of edges, at least one of the vertices has an odd degree?
My first attempt at solving this has been to show that the smallest connected graph with an even number of vertices is a graph with 2 vertices and one edge connecting them. From here, to maintain a connected graph, even number of vertices and an odd number of edges we must add both the vertices and edges by even numbers, and when adding in even numbers the degree of a vertex will not change so it must be odd.
However, this does not seem strong, so could anyone inform me on how to start a proof by contradiction?
I understand the first line of the proof by contradiction would be to assume that every vertex has even degree, but where should I go from there?
Is this not a connected graph with an even number of vertices and an odd number of edges for which an Eulerian tour exists?
Best Answer
The claim you want to prove is false -- you've given a counterexample to it yourself.
So the answer to "How would you prove ..." is: That is impossible to prove, because it is not true.