Tutte theorem

Not to be confused with Tutte homotopy theorem or Tutte's spring theorem.

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte–Berge formula.

Tutte's theorem

A graph, G = (V, E), has a perfect matching if and only if for every subset U of V, the subgraph induced by V − U has at most |U| connected components with an odd number of vertices.[1]

Proof

First we write the condition:

(*) \qquad \forall U \subseteq V, \quad o(G-U)\le|U|

where o(X) denotes the number of odd components of the subgraph induced by X.

Necessity of (∗): Consider a graph G, with a perfect matching. Let U be an arbitrary subset of V. Delete U. Let C be an arbitrary odd component in G − U. Since G had a perfect matching, at least one vertex in C must be matched to a vertex in U. Hence, each odd component has at least one vertex matched with a vertex in U. Since each vertex in U can be in this relation with at most one connected component (because of it being matched at most once in a perfect matching), o(G − U) ≤ |U|.[2]

Sufficiency of (∗): Let G be an arbitrary graph satisfying (∗), and assume for a contradiction that it has no perfect matching. Consider the expansion of G to G∗, a maximally imperfect graph, in the sense that G is a spanning subgraph of G∗, but adding an edge to G∗ will result in a perfect matching. We observe that G∗ also satisfies condition (∗) since G∗ is G with additional edges. Let U be the set of vertices of G∗ of degree |V| − 1. It can be shown through extensive case analysis that, if U is deleted, the remaining graph must form a disjoint union of complete graphs (each component is a complete graph). At most |U| of these complete graphs can be odd, so it is possible to match one vertex in each odd complete graph to a vertex in U, to match the remaining (evenly many) vertices in each complete graph among themselves, and to match the remaining vertices in U among themselves. The construction of a perfect matching in the imperfect graph G∗ contradicts the assumption that G has no perfect matching, so it does have a perfect matching and the theorem follows.[2]

See also

Notes

  1. ↑ Lovász & Plummer (1986), p.  84; Bondy & Murty (1976), Theorem 5.4, p. 76.
  2. ↑ 2.0 2.1 Bondy & Murty (1976), pp. 76–78.

References