One-factor

of a graph

Suppose is a (simple) graph. A matching in is a set of pairwise-disjoint edges in . A one-factor or spanning matching is a set of edges such that every vertex of occurs in exactly one edge.

Not every graph has a one-factor. One obvious necessary condition is that has no connected component with an odd number of vertices. However this is not a sufficient condition. The smallest graph connected with an even number of vertices but no one-factor is:

Figure: o110060a

One-factors were first studied by W.T. Tutte, who proved the following characterization. If is any subset of the vertex set of , let denote the graph constructed from by deleting and all edges touching members of . The components of are odd or even according as they have an odd or even number of vertices. Write for the number of odd components of .

Tutte's theorem [a6]: contains a one-factor if and only if whenever .

A consequence is that for even, any regular graph of degree on vertices has a one-factor.

A bridge in a graph is an edge whose deletion disconnects .

Petersen's theorem [a4]: A bridgeless cubic graph contains a one-factor.

This has been generalized by T. Schönberger [a5], who proved that every edge of a bridgeless cubic graph lies in a one-factor. C. Berge [a1] and A.B. Cruse [a3] proved another generalization. If is any set of vertices of , let be the number of edges of with exactly one end-point in .

The Berge–Cruse theorem: If is a regular graph of degree with an even number of vertices, and if for all odd-order subsets of , then each edge of belongs to some one-factor.

Consequences are [a3]:

1) if is a regular graph of degree with vertices and ( odd) or ( even), then every edge of belongs to some one-factor;

2) if is a regular graph of valency with vertices and , then contains at least

disjoint one-factors.

A number of results have been proved concerning whether a graph of a certain description (usually a quite sparse graph) contains a one-factor.

Important references include [a2], and [a7].

References

[a1]	C. Berge, "Graphs and hypergraphs" , North-Holland (1973) (Translated from French)
[a2]	J. Bosák, "Decomposition of graphs" , Kluwer Acad. Publ. (1990)
[a3]	A.B. Cruse, "A note on one-factors in certain regular multigraphs" Discrete Math. , 18 (1977) pp. 213–216
[a4]	J. Petersen, "Die Theorie der regulären Graphes" Acta Math. , 15 (1981) pp. 193–220
[a5]	T. Schönberger, "Ein Beweis des Peterschen Graphensatzes" Acta Sci. Math. Szeged , 7 (1934) pp. 51–57
[a6]	W.T. Tutte, "The factorizations of linear graphs" J. London Math. Soc. , 22 (1947) pp. 459–474
[a7]	W.D. Wallis, "One-factorizations" , Kluwer Acad. Publ. (1997)