5.1 Basic definitions and theorems
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 5.1. (Tutte's theorem): A graph G has got a 1-factor iff
