View source for One-factor

{{TEX|done}}
''of a graph''

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

Not every graph $G$ has a one-factor. One obvious necessary condition is that $G$ 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:

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/o110060a.gif" />

Figure: o110060a

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

Tutte's theorem [[#References|[a6]]]: $G$ contains a one-factor if and only if $\phi(W)\leq|W|$ whenever $W\leq V(G)$.

A consequence is that for $n$ even, any [[regular graph]] of degree $n-1$ on $2n$ vertices has a one-factor.

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

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

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

The Berge–Cruse theorem: If $G$ is a regular graph of degree $d$ with an even number of vertices, and if $z_G(W)\leq d-1$ for all odd-order subsets $W$ of $V(G)$, then each edge of $G$ belongs to some one-factor.

Consequences are [[#References|[a3]]]:

1) if $G$ is a regular graph of degree $d$ with $2m$ vertices and $d\geq m$ ($m$ odd) or $d\geq m-1$ ($m$ even), then every edge of $G$ belongs to some one-factor;

2) if $G$ is a regular graph of valency $d$ with $m$ vertices and $d\geq m\geq2$, then $G$ contains at least

$$d-m+2\left\lfloor\frac{5(m+5)}{112}\right\rfloor$$

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 [[#References|[a2]]], and [[#References|[a7]]].

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