# Proof that no Eulerian Tour exists for graph with even number of vertices and odd number of edges

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?

• Yes, the graph you indicated in your edit is a good example of an Eulerian graph with an even number of vertices and an odd number of edges.
– bof
Commented Nov 19, 2014 at 1:48
• For the question in the first sentence, not the question in the title: assume all the vertices have even degree, use the handshaking lemma, and check divisibility by $4$.
– user856
Commented Nov 21, 2014 at 17:24