CSDS 455: Applied Graph Theory
Homework 4
For this assignment, you will need to look up definitions for matchings in non-bipartite graphs and generalizations of matchings called k-factors.
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.
