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

Reading: Chapters 3 and 4

Problems:

1. Prove that a tree with at least 3 vertices always has a vertex v of degree at least two such that all but possibly one of v's neighbors are leaves.

2. Show that a disconnected graph with n vertices can have at most (n-1)(n-2)/2 edges.

3. Determine whether the two graphs below are Hamiltonian. That is, either find a Hamiltonian Cycle or prove one cannot exist.

                

4. Prove that if D is a directed graph whose vertices all have d_in(v) at least k > 0, then there is a directed cycle of length at least k+1.

5. Prove that if D is a directed graph such that each vertex v has d_in(v) >= n/2 and d_out(v) >= n/2, then D is Hamiltonian.
   (Hint: The previous problem is useful. Consider the longest directed cycle, C, and the longest directed path formed among those vertices not in C. Show that you can make C larger.)

Solutions