# Proving a connected graph cannot have only even-degree vertices

I want to prove that a connected graph with m edges and n vertices must have at least one vertex of odd degree. In particular, I want to prove this for a graph of 53 edges and 11 vertices; but also in general, is there a way to prove this for a more general case, given a set of parameters for m and n?

• This isn't true. Consider the complete graph $K_3$ with $3$ vertices and $3$ edges. Each vertex has degree $2$. – Mike Pierce Nov 22 '14 at 0:18

• @cerremony This is only my guess, but I think that there are very very few cases where all the graphs with $n$ nodes and $m$ edges have an odd degree node. – Exodd Nov 22 '14 at 18:30