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