P1) 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) 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) Given.a connectd graph G = (V,E) with n vertices and m edges.
CSE421: Design and Analysis of Algorithms
April 8, 2020
Homework 2
Shayan Oveis Gharan
Due: April 16, 2019 at 11:59 PM
a) 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.
b) 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
P4)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.
