1factor

In graph theory, a 1-factor of a graph G is a spanning subgraph in which every vertex has degree exactly 1. Equivalently, it is a perfect matching: a set of edges that covers every vertex of G exactly once. A graph can contain a 1-factor only if it has an even number of vertices.

If G has n vertices and n is even, a 1-factor consists of n/2 edges. For example, in the complete graph K_n with n even, a 1-factor corresponds to a perfect matching, and the number of distinct 1-factors is (n−1)!! = (n−1)(n−3)…3·1.

1-Factorization refers to a decomposition of the edge set of a graph into edge-disjoint 1-factors. A graph that admits such a decomposition is said to be 1-factorable. A standard result is that complete graphs K_{2m} have a 1-factorization into 2m−1 1-factors. Regular bipartite graphs also admit a 1-factorization: a k-regular bipartite graph can be decomposed into k perfect matchings.

Existence of a 1-factor is characterized by matching theory. A graph G has a 1-factor if and only if it contains a perfect matching, which can be characterized by Tutte’s theorem in general graphs and Hall’s marriage theorem for bipartite graphs. In practice, perfect matchings can be found with polynomial-time algorithms such as Edmonds’ blossom algorithm, or simpler methods in bipartite graphs.

Applications of 1-factors include scheduling round-robin tournaments, experimental design, and network design, where a perfect matching represents an arrangement that pairs every participant or component exactly once. See also matching (graph theory) and 1-factorization.