CSDS 455: Applied Graph Theory
Homework 5
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 G0 where we take G and replace
each vertex v of G with a Kd(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.
