## 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.