20
$\begingroup$

I'm having a bit of a trouble with the below question

Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$.
Prove that the number of vertices of odd degree in any graph $G$ is even.

  • 0
    http://en.wikipedia.org/wiki/Handshaking_lemma2012-08-12
  • 16
    The sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices.2012-08-12
  • 6
    @Mike: that's an answer, not a comment!2012-08-12
  • 0
    @BenMillwood Heh. Not sure how formal of a proof that is. That's why I left it as a comment and not an answer.2012-08-12
  • 7
    @Mike What's informal about it? Not enough instances of $G$, $v$, and $2n+1$? Don't fall into the trap of thinking that good mathematics has to be riddled with symbols.2012-08-13
  • 0
    @Mike I tried to formalize it.2013-11-20

7 Answers 7