[Solved] CSDS455 Homework5

Problem 1: Prove that if q(G − S) ≤ |S| for all S ⊆ V (G), then G as a 1-factor. (This is half of Tutte’s Theorem.)

Problem 2: Given graph G and integer k ≤ δ(G). Create a new graph G⁰ where we take G and replace each vertex v of G with a K_{d(v),d(v)−k} (a complete bipartite graph with d(v) vertices in one bipartition and d(v) − k vertices in the other. We will call the d(v) side A(v) and the d(v) − k side B(v). For each edge uv of G, H will have an edge connecting one vertex of A(u) with one vertex of A(v). Every vertex of A(v) will have exactly one such edge. For example, if G has the edge:

and k = 2 then H has:

Prove that G contains a k-factor if and only if H contains a 1-factor.