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?

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

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

  • $\begingroup$ 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.) $\endgroup$ – cerremony Nov 22 '14 at 18:03
  • $\begingroup$ @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. $\endgroup$ – Exodd Nov 22 '14 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.