Description
1. Let d be the maximum degree of the vertices in a graph G. Prove that we can color G with
d + 1 colors. Hint: by induction.
2. Consider this statement: In any directed graph G = (V, E), when DFS visits a vertex u ∈ V ,
then every undiscovered vertex v such that u has a path to v must be discovered before
DFS returns from u. Is this statement true or false? If true, give a proof; if false, give a
counterexample.
3. Consider this statement: In any undirected graph G = (V, E), there must be an even number
of vertices whose degree is odd. Is this statement true or false? If true, give a proof; if false,
give a counterexample.
4. Consider the problem of determining whether an undirected graph G = (V, E) contains a
triangle (cycle of length three).
(a) Give an O(|V |
3
) to find a triangle if one exists.
(b) Improve your algorithm to run in time O(|V | · |E|). You may assume |V | ≤ |E|.
5. You are given a weighted graph and its minimum spanning tree. There are n vertices and m
edges in the graph.
(a) Design a polynomial-time algorithm that finds the smallest change in the weight of a
non-MST edge that would cause a change in the MST.
(b) Analyze the runtime of your algorithm in terms of n and m.
