Proving a connected graph cannot have only even-degree vertices

Question

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?

Answer 1

As already shown, it's not true in general (any simple cycle has every node of even degree).

The case with 53 edges and 11 vertices is particular, since 11*10/2=55, so it's a complete graph without 2 edges, and it's easy to prove that there exists a node with odd degree, since there are basically only 2 cases.

But this reasoning fails very often. For example there exists a graph with 11 vertices and 52 edges that has no nodes of odd degree (try to prove it by yourself ;) )