Kfactors

In graph theory, a k-factor of a graph G is a spanning subgraph in which every vertex has degree exactly k. If G has n vertices, a k-factor can exist only when nk is even, since the sum of the degrees in the subgraph must be twice the number of edges. A necessary condition is also that the original graph has minimum degree at least k, since no vertex can gain degree beyond what its incident edges allow.

Special cases include a 1-factor, which is a perfect matching, and a 2-factor, which is a spanning subgraph where every vertex has degree 2 and is therefore a disjoint union of cycles. The study of k-factors intersects with core results in matching theory. For example, Petersen’s theorem guarantees that every 3-regular bridgeless graph has a 1-factor. In bipartite graphs, regularity implies stronger decomposition results: a k-regular bipartite graph can be decomposed into k disjoint perfect matchings, a k-factorization.

Existence criteria for general k-factors are captured by Tutte’s f-factor theorem, which provides necessary and sufficient conditions for the existence of an f-factor for a given function f on the vertex set. In practice, checking these conditions or constructing a k-factor can be done in polynomial time using reductions to maximum matching or flow problems.

Applications of k-factors include network design, scheduling, and the study of graph decompositions. See also perfect matching, f-factor, and regular graphs.