Due: Thursday October 19 at the beginning of class (10am).

Reading: Chapters 3 and 4

Problems:

1. Prove that a graph with n vertices, m edges and p connected components contains at least m-n+p cycles.

2. Prove that a graph always has an orientation in which every vertex v satisfies:
           | d_in(v) - d_out(v) | <= 1 .
   (Hint: Euler)

3. Use the Matrix-Tree Theorem to calculate the number of spanning trees of the graph below.
   

4. Draw all of the spanning trees of the graph above. (Draw small.)

5. Recall that a directed graph is unilaterally connected if given any two vertices, one is accessible from the other. Prove that a directed graph D is unilaterally connected if and only if D has a spanning directed walk (a directed walk that includes all vertices, perhaps more than once).

Solutions