Discrete Mathematics - Mathematics 210 - Fall 2010

1. Prove that in every graph, the sum of the degrees of the vertices equals twice the number of edges.
2. Prove that every graph has an even number of odd vertices. (Hint: use the above problem.)
3. Prove that if a graph has no odd vertices, then it has no bridges. (Hint: use the above problem.)
4. Suppose a graph has exactly two odd vertices, v and w. Prove that if deg(v) > 1, then there is a non-bridge edge incident with v. (Hint: use problem 2.)