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.