Due: Tuesday October 3 at the beginning of class (10am).

Reading: Chapters 1 and 2 (skip Prufer codes pages 10-12)

Problems:

1. Prove the following by induction.
   If the degree of every vertex in a graph G is at least 2, then G contains a cycle.

2. For which values of n do there exist graphs with n vertices for which both G and G are connected?

3. Let a to b be two distinct vertices. Prove formally that if there is a walk from a to b in G, then there is a path from a to b in G.

4. Show that there is no tree with exactly one leaf (vertex of degree 1).

5. Show that a graph with n vertices and e edges always has a vertex of degree at least &lceil 2e/n &rceil .

6. Show that G is a tree if and only if G is connected but removing any edge from G disconnects it.

7. Show that G is a tree if and only if G is acyclic but adding any edge to G introduces a cycle.

8. Suppose that G has a subset of vertices S such that G\S has |S| + 1 connected components. Show that G is not Hamiltonian.