5.3.1. 1-factorable graphs
- Every 1-regular graph is 1-factorable.
- Only regular graphs of even order can be 1-factorable.
- A 2-regular graph is 1-factorable iff its every component is an even cycle.
The situation for k-regular graphs, , in general or even only 3-regular graphs is
considerable more complicated:
By Petersen theorem, every bridgeless cubic graph contains a 1-factor. (Exercise)
Consequently, every bridgeless cubic graph can be factored into a 1-factor and a 2-factor.
However, not every bridgeless cubic graph is 1-factorable:
For example, the Petersen graph is a bridgless cubic graph and it is not 1-factorable.
First, we show two classes of 1-factorable graphs:
Let U be a nonempty set of vertices of a graph G.
Then U is said to be nondeficient if for every nonempty subset S of U.
In a graph G, a nonempty subset of
is said to be
matched to a subset
of
disjoint from
if there exists
a matching M in G such that each edge of M is incident
with a vertex of
and a vertex of
, and every vertex of
is incident
with an edge of M, as is every vertex of
.
If , where
is also a matching in G, then we also
say
is matched under
to
.
Theorem 5.4. Let G
be a bipartite graph with partite sets and
. The set
can be matched
to a subset of
iff
is
nondeficient.
Proof.



Then every nonempty subset
S of can be matched under
to some subset of
,
implying that
.
So, is nondeficient.
To verify the converse, let G be a bipartite
graph for which is
nondeficient and suppose that
cannot be
matched to a subset of
.
Let M be a maximum matching in G.
By assumption, there is a vertex v in that is an M-unsaturated
vertex.
Let S be the set of all vertices of G that are connected to v by an M-alternating path.
Since M is a maximum matching, an application of Theorem 4.1. yields v as the only M-unsaturated vertex in S.
Let and let
.
Using the definition of the set S, together with
the fact that no vertex of is M-unsaturated
vertex, we conclude that
is matched
under M to
.
Therefore, .
Furthermore, for every , the
graph G contains an M-alter-nating
path so that
.
Thus and
.
This, however, contradicts the fact that is
nondeficient.
Theorem 5.5. (König, 1916): Every regular bipartite graph of degree is 1-factorable.
Proof.
We will use induction on k.
The result is obvious for .
Assume that every regular bipartite graph of degree ,
, is 1-factorable, and let G be a
regular bipartite graph of degree k, where
and
are the partite sets of G.
We first show that is nondeficient.
Let S be a nonempty subset of of . The number of edges of G incident with the vertices of S
is
.
These edges are also
incident with the vertices of .
Hence, so that
. So,
is
nondeficient.
This implies, by the Theorem 8.22 that can be matched to a subset of
.
Since G is regular of positive degree, .
Therefore, G has a 1-factor. We will denote it by F.
The removal the edges of F from G results
in a bipartite graph G' that is regular of
degree .
By the inductive hypothesis, G' is 1-factorable, implying that G is also 1-factorable.
Theorem 5.6. The complete graph is 1-factorable.
Proof.
The result is
obvious for . So we assume that
.
Denote the
vertex set of by
and arrange the vertices
in a regular
-gon, placing
in the center.
Join every two
vertices by a straight line segment, producing .
For , define the 1-factor
to consist of the edge
together with all
edges perpendicular to
.
Then , so
is 1-factorable.
Obtain that we can draw the different factors to the other ones. We call this as cyclic factorization.