1. (15 points) Prove by induction that any connected, undirected graph G = (V,E) with no cycles and V > 0 has exactly V − 1 edges (and is therefore a tree).

2. (15 points) Prove by induction over the number of edges that any simple undirected graph G = (V,E) has at least E − V + 1 cycles.

3. (10 points) Consider the graph G given below and list all its topological orders:

4. (15 points) Prim’s algorithm for finding a minimum spanning tree starts from an arbitrary vertex and grows a tree from that vertex. At each step, it adds the lowest-weight edge not yet in the tree that (1) is incident on one of the vertices already in the tree and (2) does not create a cycle.   Work out Prim’s algorithm for the graph and find a minimum spanning tree.

5. (15 points) Prove that any undirected graph with maximum degree k is k + 1 colorable.

6. (10 points) Determine if the following graphs are Eulerian graphs or not. (Eulerian graph is a graph containing eulerian cycle).

(a) Graph K5

(b) Peterson Graph

7. (20 points) Decide for the following graphs if they are Hamiltonian, have Hamiltonian path or nothing.

(a) G1

(b) G2

(c) G3