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.

Suppose the  can be matched to a subset of  under a matching .

 

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.