Description
Please see https://courses.cs.washington.edu/courses/cse421/18wi/grading.html for general guidelines about Homework problems.
Most of the problems only require one or two key ideas for their solution. It will help you a lot
to spell out these main ideas so that you can get most of the credit for a problem even if you err
on the finer details. Please justify all answers.
P1) (20 points) Let G be a tree. Use induction to prove that we can color vertices of G with 2
colors such that the endpoints of every edge have opposite colors. For example, in the following
picture we give a coloring of the given tree with black and white.
P2) (20 points) Given a connected undirected graph G = (V, E), design an O(m+n)-time algorithm
to find a vertex in G whose removal does not disconnect G. Note that as a consequence this
algorithm shows that every connected graph contains such a vertex.
P3) (25 points) Given.a connectd graph G = (V, E) with n vertices and m edges.
a) (10 points) Design an O(m +n) time algorithm that outputs the vertices of a cycle of G. If
G has no cycles, your algorithm should output “no cycle”. For example, given the following
graph your algorithm may output 1, 2, 4, 3, 1.
1
2
3
4
b) (10 points) We say a tree T is a spanning tree of G if T has n − 1 edges and edges of T
are a subset of E. Suppose that m ≥ n. Prove that G has at least 3 spanning trees. For
example, the following are 3 spanning trees of the above graph (note that the above graph
has 7 spanning trees):
c) Given a connected graph G = (V, E) with m ≥ n, design an O(m + n) time algorithm that
outputs three spanning trees of G. For example, in the above examples, your algorithm
may output as follows (note that the format of the output is not important):
(1, 2),(2, 3),(3, 4)
(1, 2),(2, 3),(2, 4)
(1, 2),(1, 3),(3, 4)
2-1
1
2
3
4 1
2
3
4 1
2
3
4
P4) (20 points) Given a graph G = (V, E) with n vertices such that the degree of every vertex
of G is at most k. Furthermore, assume that in every connected component of G there is a
vertex of degree smaller than k. Show that we can color vertices of G with k colors such that
the endpoints of every edge of G have distinct colors. See the following graph for an example
(here k = 3)
P5) Extra Credit: Prove that we can color the edges of every graph G with two colors (red
and blue) such that, for every vertex v, the number of red edges touching v and the number
of blue edges touch v differ by at most 2.
2-2
