Onefactor

Onefactor, in graph theory commonly written as 1-factor, refers to a perfect matching in a graph. A 1-factor of a graph G = (V,E) is a set M ⊆ E such that every vertex in V is incident with exactly one edge from M. Equivalently, M partitions the vertex set into disjoint pairs, covering all vertices precisely once. If a graph has a 1-factor, it is said to contain a perfect matching.

A related concept is a 1-factorization, which is a decomposition of the graph’s edge set into pairwise disjoint 1-factors. A graph that admits a 1-factorization is often described as being 1-factorable. Complete graphs and complete bipartite graphs provide classical examples: the complete graph on an even number of vertices, K2n, can be decomposed into 2n−1 disjoint 1-factors, yielding a standard round-robin tournament schedule. The complete bipartite graph Kn,n can be decomposed into n disjoint 1-factors, corresponding to n rounds of pairings between the two vertex parts.

Existence and computation of 1-factors depend on the graph’s structure. Not every even-vertex graph has a 1-factor, but several broad results guarantee existence under specific conditions. In bipartite graphs, Hall’s marriage theorem gives necessary and sufficient criteria for a perfect matching. For general graphs, algorithms based on maximum matching, such as Edmonds’ blossom algorithm, can determine whether a perfect matching exists and, if so, construct it.

Applications are common in scheduling, network design, and combinatorial design. A 1-factorization yields efficient round-robin schedules and supports constructions in experimental design and coding theory. The concept remains a foundational tool in graph theory, highlighting the interplay between matching theory and graph decomposition.