Discrete Mathematics - Mathematics 140 - Fall 2005

Turn in the following problems:

1. Suppose G = (V, E) is a graph with V = {a, b, c, d, e}. Suppose abcdacea is an Eulerian circuit. Find the degree of each vertex.
2. Suppose G = (V, E) is a graph with V = {a, b, c, d}. Suppose abdacb is an Eulerian path. Find the degree of each vertex.
3. Prove that if a graph G has an Eulerian circuit, then every vertex of G has even degree.
4. Prove that if a graph G has an Eulerian non-closed path, then G has exactly two vertices of odd degree. (Recall that a non-closed path is a path that's not a circuit.)

(We will prove the converses of 3 and 4 in class on Monday.)