# 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

## 1 Answer

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 ;) )

• Thanks, I just wanted to know abut this particular case, but I was wondering if there was some general rule for determining whether a particular graph has any vertices of odd degree. (In particular I wanted to know this in relation to whether a graph is Eulerian or not; I know that every vertex in a graph must be of an even degree in order for a graph to be Eulerian, and so I wanted to know if there was a more general method for proving that a graph with a certain number of vertices and a certain number of edges is Eulerian or not, beyond simply creating a proof for that particular case.) – cerremony Nov 22 '14 at 18:03
• @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