9.6. Factors of graphs.

A factor of a graph is a subgraph whose vertex set is that of the whole graph. If every vertex of a factor has degree r then we call it an r-factor. ( An r-factor is an r-regular spanning subgraph).

Fact: If a graph G has a 1-factor H then the order of G is even.

The problem: If we delete some vertices then the remainder graph behaves " badly". We call a component of a disconnected graph as odd (even) if it has odd (even) number of vertices. For a graph H we denote by the number of its odd components.

If G has a 1-factor H and we delete a set S of vertices of G, then in a component C of

  • an even number of vertices are on edges of H contained in C and
  • the other vertices of C are on edges of H joining a vertex of C to a vertex of S.

In particularly, for every odd component C of there is an edge of H joining a vertex of C to a vertex of S.

The edges of H are independent, so this implies that the graph has at most odd components, one for each vertex in S.

Is the above necessary condition also sufficient?

Theorem 9.10. (Tutte's theorem): A graph G has got a 1-factor iff

Proof.

We know that the condition is necessary.

We shall prove the sufficiency by induction on the order of G.

  • For there is nothing to prove.
  • Let G be a graph of order at least one, satisfying and suppose that the theorem holds for graphs of smaller order.

We will define the following sets:

  • be a non-empty set for which equality holds in i.e.
  • the odd components of ,
  • be the even components of ,

If the theorem is true and G does contain a 1-factor F then the following facts hold:

  • For each there is at least one edge of F that joins a vertex of to a vertex in .
  • Since , for each there is exactly one such edge, say , where and .
  • Each contains a 1-factor, (a subgraph of F).
  • Each contains a 1-factor, (a subgraph of F).
  • The edges form a complete matching from into the set .

Can we find an which has all the properties described above? It is not even clear that there is such a set . We prove this fact first.

With the condition implies that G has an even order.

Let , where . Then has odd order, so it has at least one odd component.

Since , so has exactly one odd component. Hence for every we have equality in , which establishes the existence of .

Let be the maximal non-empty subset of for which equality holds.

Statement 9.11.: Each has a 1-factor.

Proof.

Let then

,

and so

Hence by the induction hypothesis has a 1-factor.

Statement 9.12.: If then has a 1-factor.

Proof.

Assume that this statement is false. Then by the induction hypotesis there is a set such that

.

Since

this implies that

Consequently

so in we have equality for the set as well.

This contradicts the maximality of .

Statement 9.12.: G contains m independent edges of the form

Proof.

Let us consider the bipartite graph with two vertex classes and . is joined to a vertex  iff G contains an edge from s to .

The statement is true iff H has a matching from . We will use the Hall's theorem. To a given we put . Then implies that

.

Hence the graph H satisfies Hall's condition, so it has 1-factor.

To complete the proof we put together the information of the last three statements:

  • We start with the m independent edges 
  • Adding to this set of edges a 1-factor of each and

Adding a 1-factor of each 

So we completed the theorem.