Exam 2 sample problems

Be sure to justify your answers.

1. Which of the following graphs isomorphic?

2. The edge chromatic number of a graph is the minimum number of colors necessary to color the edges so that no two edges touching a vertex get the same color. An independent set is a set of vertices which do not induce any edges.

Find the edge chromatic number of and a maximum independent set in the Petersen Graph above.

3. Which of the following graphs are planar?

4. Prove that a tree contains at most one perfect matching. How many perfect matchings does a cycle on n vertices contain?

5. Prove that a tree T contains a unique {u,v}-path for every pair of vertices u,v in V(T).

6. Show that a graph G is bipartite if and only if every induced subgraph H of G contains an independent set of size at least |V(H)|/2.

7. Show that a connected graph with exactly |V| edges has exactly one cycle.