Tutte theorem

Last updated
Example of a graph and one of its perfect matching (in red). Perfect matching 1.jpg
Example of a graph and one of its perfect matching (in red).

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs.[ clarification needed ] It is a special case of the Tutte–Berge formula.

Contents

Intuition

An graph (or a component) with an odd number of vertices cannot have a perfect matching, since there will always be a vertex left alone. No perfect matching in odd graphs.svg
An graph (or a component) with an odd number of vertices cannot have a perfect matching, since there will always be a vertex left alone.

Our goal is to characterize all graphs that do not have a perfect matching. Let us start with the most obvious case of a graph without a perfect matching: a graph with an odd number of vertices. In such a graph, any matching leaves at least one unmatched vertex, so it cannot be perfect.

A slightly more general case is a disconnected graph in which one or more components have an odd number of vertices (even if the total number of vertices is even). Let us call such components odd components. In any matching, each vertex can only be matched to vertices in the same component. Therefore, any matching leaves at least one unmatched vertex in every odd component, so it cannot be perfect.

Next, consider a graph G with a vertex u such that, if we remove from G the vertex u and its adjacent edges, the remaining graph (denoted G  u) has two or more odd components. As above, any matching leaves, in every odd component, at least one vertex that is unmatched to other vertices in the same component. Such a vertex can only be matched to u. But since there are two or more unmatched vertices, and only one of them can be matched to u, at least one other vertex remains unmatched, so the matching is not perfect.

Finally, consider a graph G with a set of vertices U such that, if we remove from G the vertices in U and all edges adjacent to them, the remaining graph (denoted G  U) has more than|U| odd components. As explained above, any matching leaves at least one unmatched vertex in every odd component, and these can be matched only to vertices of U - but there are not enough vertices on U for all these unmatched vertices, so the matching is not perfect.

We have arrived at a necessary condition: if G has a perfect matching, then for every vertex subset U in G, the graph G  U has at most |U| odd components. Tutte's theorem says that this condition is both necessary and sufficient for the existence of perfect matching.

Tutte's theorem

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

Proof

First we write the condition:

where denotes the number of odd components of the subgraph induced by .

Necessity of (∗): This direction was already discussed in the section Intuition below, but let us sum up here the proof. 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), odd(G  U)  |U|. [2]

Sufficiency of (∗): Let G be an arbitrary graph with no perfect matching. We will find a so-called Tutte violator, that is, a subset S of V such that |S| < odd(G  S). We can suppose that G is edge-maximal, i.e., G + e has a perfect matching for every edge e not present in G already. Indeed, if we find a Tutte violator S in edge-maximal graph G, then S is also a Tutte violator in every spanning subgraph of G, as every odd component of G  S will be split into possibly more components at least one of which will again be odd.

We define S to be the set of vertices with degree |V|  1. First we consider the case where all components of G  S are complete graphs. Then S has to be a Tutte violator, since if odd(G  S)  |S|, then we could find a perfect matching by matching one vertex from every odd component with a vertex from S and pairing up all other vertices (this will work unless |V| is odd, but then is a Tutte violator).

Now suppose that K is a component of G  S and x, y  K are vertices such that xy  E. Let x, a, b  K be the first vertices on a shortest x,y-path in K. This ensures that xa, ab  E and xb  E. Since a  S, there exists a vertex c such that ac  E. From the edge-maximality of G, we define M1 as a perfect matching in G + xb and M2 as a perfect matching in G + ac. Observe that surely xb  M1 and ac  M2.

Let P be the maximal path in G that starts from c with an edge from M1 and whose edges alternate between M1 and M2. How can P end? Unless we arrive at 'special' vertex such as x, a or b, we can always continue: c is M2-matched by ca, so the first edge of P is not in M2, therefore the second vertex is M2-matched by a different edge and we continue in this manner.

Let v denote the last vertex of P. If the last edge of P is in M1, then v has to be a, since otherwise we could continue with an edge from M2 (even to arrive at x or b). In this case we define C:=P + ac. If the last edge of P is in M2, then surely v  {x, b} for analogous reason and we define C:=P + va + ac.

Now C is a cycle in G + ac of even length with every other edge in M2. We can now define M:=M2 Δ C (where Δ is symmetric difference) and we obtain a perfect matching in G, a contradiction.

Equivalence to the Tutte-Berge formula

The Tutte–Berge formula says that the size of a maximum matching of a graph equals . Equivalently, the number of unmatched vertices in a maximum matching equals .

This formula follows from Tutte's theorem, together with the observation that has a matching of size if and only if the graph obtained by adding new vertices, each joined to every original vertex of , has a perfect matching. Since any set which separates into more than components must contain all the new vertices, (*) is satisfied for if and only if .

In infinite graphs

For connected infinite graphs that are locally finite (every vertex has finite degree), a generalization of Tutte's condition holds: such graphs have perfect matchings if and only if there is no finite subset, the removal of which creates a number of finite odd components larger than the size of the subset. [3]

See also

Notes

  1. Lovász & Plummer (1986), p.  84; Bondy & Murty (1976), Theorem 5.4, p. 76.
  2. Bondy & Murty (1976), pp. 76–78.
  3. Tutte, W. T. (1950). "The factorization of locally finite graphs". Canadian Journal of Mathematics. 2: 44–49. doi: 10.4153/cjm-1950-005-2 . MR   0032986. S2CID   124434131.

Related Research Articles

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M.

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

In graph theory, a vertex subset is a vertex separator for nonadjacent vertices a and b if the removal of S from the graph separates a and b into distinct connected components.

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

<span class="mw-page-title-main">Tutte–Berge formula</span> Characterization of the size of a maximum matching in a graph

In the mathematical discipline of graph theory the Tutte–Berge formula is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte theorem on perfect matchings, and is named after W. T. Tutte and Claude Berge.

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

<span class="mw-page-title-main">Petersen's theorem</span>

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.

<span class="mw-page-title-main">Gallai–Edmonds decomposition</span> Partition of the vertices of a graph giving information on the structure of maximum matchings

In graph theory, the Gallai–Edmonds decomposition is a partition of the vertices of a graph into three subsets which provides information on the structure of maximum matchings in the graph. Tibor Gallai and Jack Edmonds independently discovered it and proved its key properties.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

Deficiency is a concept in graph theory that is used to refine various theorems related to perfect matching in graphs, such as Hall's marriage theorem. This was first studied by Øystein Ore. A related property is surplus.

References