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.