Description
Problem 1 (15+1 points)
Recall that a graph is k-colorable if it is possible to assign each vertex to one of k colors such that
the two endpoints of every edge are assigned different colors. Prove that a graph G = (V, E) is 2
k
–
colorable if and only if E can be partitioned into k sets E1, . . . , Ek such that for every 1 ≤ i ≤ k,
Gi = (V, Ei) is a bipartite graph.
Problem 2 (25+2 points)
(a) (15+1 points) Suppose G = (A ∪ B, E) is a bipartite graph. Recall the neighborhood of a
set of vertices S ⊆ A is defined as N(S) = {v ∈ B : ∃u ∈ S.{u, v} ∈ E}. The deficiency
of S ⊆ A is defined as def(S) = max{0, |S| − |N(S)|}. Then, the deficiency of G is the
maximum definiciency of any subset of A:
def(G) = max
S⊆A
def(S).
Finally, recall a matching in G is a set of edges M ⊆ E such that no two edges in M are
incident on the same vertex.
Prove that the maximum number of edges in a matching contained in E is |A| − def(G).
(Hint: Try forming a larger graph by adding def(G) new vertices to B and connect each new
vertex to all vertices in A.)
(b) (10+1 points) The standard deck of playing cards has 4 suits of 13 ranks, for a total of 52
cards. Suppose we remove an arbitrary 13 cards and place the remaining 39 cards in a grid
with 3 rows of 13 cards per row. Prove that there is always a way to pick one card from each
column so that at least 10 distinct ranks are selected.
(Hint: Try to apply the result you proved in part (a).)