Tutte theorem
Encyclopedia
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
.
has a perfect matching if and only if
for every subset
of 
the number of connected component
s with an odd number of vertices
in the subgraph induced by
is less than or equal to the cardinality of 
.
is a necessary condition:
Consider a graph
, with a perfect matching. Let 
be an arbitrary subset of 
. Delete 
. Consider an arbitrary odd component in 
. Since 
had a perfect matching, at least one vertex in 
must be matched to a vertex in 
. Hence, each odd component has at least one vertex matched with a vertex in 
. Since each vertex in 
can be in this relation with at most one connected component (because of it being matched at most once in a perfect matching), 
.
To prove that
is sufficient:
Let
be an arbitrary graph satisfying 
. Consider the expansion of 
to 
, a maximally imperfect graph, in the sense that 
is a spanning subgraph of 
but adding an edge to 
will result in a perfect matching. We observe that 
also satisfies condition 
since 
is 
with additional edges. Let 
be the set of vertices of degree 
where 
. By deleting 
, we obtain a disjoint union of complete graphs (each component is a complete graph). A perfect matching may now be defined by matching each even component independently, and matching one vertex of an odd component 
to a vertex in 
and the remaining vertices in 
amongst themselves (since an even number of them remain this is possible). The remaining vertices in 
may be matched similarly, as 
is complete.
This proof is not complete. Deleting
may obtain a disjoint union of complete graphs, but the case where it does not is the more interesting and difficult part of the proof.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
with perfect matchings. It is a generalization of the marriage theorem
Marriage theorem
In mathematics, Hall's marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets...
and is a special case of the Tutte-Berge formula
Tutte-Berge formula
In the mathematical discipline of graph theory the Tutte–Berge formula, named after William Thomas Tutte and Claude Berge, is a characterization of the size of a maximum matching in a graph...
.
Tutte's theorem
A given graph has a perfect matching if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
for every subset
of the number of connected componentConnected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
s with an odd number of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
in the subgraph induced by
is less than or equal to the cardinality of .Proof
To prove that is a necessary condition:Consider a graph
, with a perfect matching. Let be an arbitrary subset of . Delete . Consider an arbitrary odd component in . Since had a perfect matching, at least one vertex in must be matched to a vertex in . Hence, each odd component has at least one vertex matched with a vertex in . Since each vertex in can be in this relation with at most one connected component (because of it being matched at most once in a perfect matching), .To prove that
is sufficient:Let
be an arbitrary graph satisfying . Consider the expansion of to , a maximally imperfect graph, in the sense that is a spanning subgraph of but adding an edge to will result in a perfect matching. We observe that also satisfies condition since is with additional edges. Let be the set of vertices of degree where . By deleting , we obtain a disjoint union of complete graphs (each component is a complete graph). A perfect matching may now be defined by matching each even component independently, and matching one vertex of an odd component to a vertex in and the remaining vertices in amongst themselves (since an even number of them remain this is possible). The remaining vertices in may be matched similarly, as is complete.This proof is not complete. Deleting
may obtain a disjoint union of complete graphs, but the case where it does not is the more interesting and difficult part of the proof.