[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 Tuttes 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.