Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 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.

Any help would be very much appreciated:)

share|improve this question
    
5  
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. –  Mike Aug 12 '12 at 21:24
2  
@Mike: that's an answer, not a comment! –  Ben Millwood Aug 12 '12 at 21:34
    
@BenMillwood Heh. Not sure how formal of a proof that is. That's why I left it as a comment and not an answer. –  Mike Aug 12 '12 at 21:48
2  
@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. –  Austin Mohr Aug 13 '12 at 3:26

3 Answers 3

I'm posting Mike's comment as an answer, since he won't.

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.

share|improve this answer

Hint: What is the sum of the degrees of all vertices?

share|improve this answer

We represent $G$ by a symmetric relation on the set of points $P$, which we also call $G$, so $$G = \{(a,b), (b,a) : \text{there is an edge between } a \text{ and } b\}$$ Clearly, $\#G |2$ where $\#G$ is the number of elements in $G$. Now $$\deg (a) = \# \{(a,x): (a,x) \in G\}$$ Since we have $$\sum_{a\in P} \deg(a) = \sum_{a\in P} \# \{(a,x): (a,x) \in G\} = \#\{(x,y) : (x,y) \in G\} = \# G$$ We know $$\sum_{a\in P} \deg (a) | 2$$ From number theory we have $$\sum_{j=1}^n a_j |2 \Leftrightarrow \#\{a_j : a_j \not|\, 2\}|2$$ (the number of odd numbers in a sum is even, iff the sum is even) and setting $a_j = \deg(b_j)$ with $b_j \in P$ an enumeration of $P$, the statement follows.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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