CSDS455-Homework 4 Solved

Problem 1: In the graph drawn below, exhibit a k-factor for each k in {0,1,2,3,4}.

 

Problem 2: Let G be a k-regular, bipartite graph. Prove that G can be decomposed into r factors if and only if r divides k.

Problem 3: For each k 1, construct a k-regular simple graph having no 1-factor.