Theorem 3.5.1. Tutte–Berge Formula.
For any graph \(G\text{,}\)
\begin{equation*}
\nu(G) = \frac{1}{2}\min_{S\subseteq V(G)}\left(|V(G)|+|S|-o(G\setminus S)\right).
\end{equation*}
Section 3.5 Matchings in General Graphs
So far in this chapter, we have focused on matching problems in bipartite graphs. In this section, we will look briefly at the case of general (not necessarily bipartite) graphs. Given a graph \(H\text{,}\) a component of \(H\) is a maximal set of vertices such that any two vertices in that set can reach each other by paths. We let \(o(H)\) denote the number of components of \(H\) with an odd number of vertices. Also, for a graph \(G\) and a set \(S\subseteq V(G)\text{,}\) let \(G\setminus S\) be the graph obtained by deleting all vertices of \(S\) and all edges incident to such a vertex. You may recall that, for bipartite graphs, the appropriate “dual” problem to the problem of finding a largest matching was the problem of finding a minimum vertex cover, but that this is not true for general graphs. As it turns out, for general graphs, the appropriate dual problem involves a particular function of the cardinality and the number of odd components of \(G\setminus S\) for a subset \(S\) of \(V(G)\text{.}\)
Proof.
First, let us show that \(\nu(G) \leq \frac{1}{2}\left(|V(G)|+|S|-o(G\setminus S)\right)\) for any set \(S\subseteq V(G)\text{.}\) If \(M\) is a matching in \(G\text{,}\) then each component \(C\) of \(G\setminus S\) can contain at most \(\frac{|C|}{2}\) edges of \(M\) if \(|C|\) is even and at most \(\frac{|C|-1}{2}\) if \(|C|\) is odd. Therefore, the total number of edges of \(M\) contained within \(V(G)\setminus S\) is at most \(\frac{1}{2}|V(G)\setminus S| - \frac{1}{2}o(G\setminus S)\text{.}\) Also, the number of matching edges that have at least one endpoint within \(S\) is at most \(|S|\text{.}\) So,
\begin{equation*}
|M|\leq \frac{1}{2}|V(G)\setminus S| - \frac{1}{2}o(G\setminus S) + |S| = \frac{1}{2}\left(|V(G)|+|S|-o(G\setminus S)\right)
\end{equation*}
as required.
So, it remains to show that every graph \(G\) has a set \(S\) such that \(\nu(G) \geq \frac{1}{2}\left(|V(G)|+|S|-o(G\setminus S)\right)\text{.}\) We prove this by induction on \(|V(G)|\text{.}\) Of course, if \(G\) is disconnected, then we can apply the formula to each component of \(G\) and we are done. So, \(G\) is connected. We divide the proof into cases.
Case.
There exists a vertex \(v\) such that every matching in \(G\) of maximum cardinality saturates \(v\text{.}\)In this case, we have that \(\nu(G\setminus\{v\})=\nu(G)-1\text{.}\) By induction, we can apply the formula to \(G\setminus\{v\}\) to get a set \(T\subseteq V(G)\setminus\{v\}\) such that \(\nu(G)-1=\frac{1}{2}\left(|V(G)|-1 + |T| - o((G\setminus\{v\})\setminus T)\right)\text{.}\) We are done by letting \(S:=T\cup\{v\}\text{.}\)
Case.
For every vertex \(v\text{,}\) there exists a matching in \(G\) of maximum cardinality that does not saturate \(v\text{.}\)In this case, the graph \(G\) cannot have a perfect matching for, if it did, then every matching of maximum size would be perfect and would therefore saturate every vertex. So, \(\nu(G)< \frac{|V(G)}{2}\text{.}\) What we will prove is that, in fact, \(\nu(G)=\frac{|V(G)|-1}{2}\text{.}\) If we can do this, then \(S=\emptyset\) will be a set such that \(\nu(G) \leq \frac{1}{2}\left(|V(G)|+|S|-o(G\setminus S)\right)\) and we will be done.
We proceed by contradiction. Suppose that \(\nu(G)\leq \frac{|V(G)|-2}{2}\text{,}\) let \(M\) be a matching of maximum cardinality and let \(u,v\in V(G)\) such that \(u\) and \(v\) are not saturated by \(M\text{.}\) Among all possible choices of \(M,u\) and \(v\text{,}\) suppose that the distance between \(u\) and \(v\) (i.e. the length of the shortest path between them) is as small as possible. Recall that \(G\) is connected, and so the distance from \(u\) to \(v\) is finite. Of course, if \(uv\) is an edge, then we can add \(uv\) to \(M\) to get a larger matching, which is a contradiction. So, the shortest path from \(u\) to \(v\) contains at least one other vertex, say \(w\text{.}\) By assumption, there exists a matching in \(G\) of maximum cardinality such that \(w\) is not saturated. Choose such a matching \(M'\) such that \(|M\cap M'|\) is as large as possible.
Now, note that the distance from \(u\) to \(w\) is less than the distance from \(u\) to \(v\text{.}\) So, if \(M'\) does not saturate \(u\text{,}\) then it would contradict our choice of \(u,v,M\text{.}\) So, \(M'\) saturates \(u\) and, by a similar argument, it saturates \(v\text{.}\) Thus, since \(M\) and \(M'\) have the same cardinality, there must be a vertex \(z\neq w\) that is saturated by \(M\) but not by \(M'\text{.}\) Note that \(wz\) cannot be an edge for, if it were, then we could add this edge to \(M'\) to get a larger matching. Let \(yz\) be the edge of \(M\) containing \(z\text{.}\) The vertex \(y\) must be saturated by \(M'\) because, if not, then we could add \(yz\) to \(M'\) and get a larger matching. So, let \(xy\) be the edge of \(M'\) that saturates \(y\text{.}\) Let \(M''=\left(M'\setminus \{xy\}\right)\cup \{yz\}\text{.}\) This is a matching of the same cardinality as \(M'\) which does not saturate \(w\) (because \(w\) and \(z\) are not adjacent) such that \(|M\cap M''|> |M\cap M'|\text{,}\) which is a contradiction. So, we must have \(\nu(G)=\frac{|V(G)|-1}{2}\) which completes the proof.
Theorem 3.5.2. Tutte’s 1-Factor Theorem.
A graph \(G\) has a perfect matching if and only if \(o(G\setminus S)\leq |S|\) for every \(S\subseteq V(G)\text{.}\)Proof.
A graph \(G\) has a perfect matching if and only if \(\nu(G)=\frac{1}{2}|V(G)|\text{.}\) By Theorem 3.5.1, this holds if and only if \(o(G\setminus S)\leq |S|\) for every \(S\subseteq V(G)\text{.}\)
Note that the Tutte–Berge Formula seems to suggest that, to compute the matching number, you may need to compute \(|V(G)|+|S|-o(G\setminus S)\) for every subset \(S\) of the vertex set, which would take an exponential number of steps. So, one cannot derive a polynomial time algorithm directly from this theorem. Similarly, Tutte’s 1-Factor Theorem does not provide a polynomial time procedure for determining whether a graph has a perfect matching. However, it does show that the problem of determining if a graph has a perfect matching is in \(\text{NP}\cap\text{co-NP}\) because it implies that there are an easily checkable certificates for showing that a graph does or does not have a perfect matching. As we have said throughout this course, showing that a problem is in \(\text{NP}\cap\text{co-NP}\) is strong evidence that the problem is polynomial-time solvable. Indeed, in the case of matching problems, there does exist a polynomial-time algorithm for general graphs; this is the famous “Blossom Algorithm” of Edmonds. We will not cover that algorithm in this course, but you should be aware of its existence.
You may recall that, for bipartite graphs, the matching polytope (i.e. the convex hull of indicator vectors of matchings) was simply equal to the set of all fractional matchings, and a similar statement holds for the perfect matching polytope, but that these statements does not hold for general graphs. However, as it turns out, one can still characterize the matching polytope of a general in terms of fractional matchings with one additional type of constraint. We will not prove the following two theorems, but they are worth being aware of. Given a set \(U\subseteq V(G)\text{,}\) let \(\partial(U)\) be the set of all boundary edges of \(U\text{;}\) i.e. edges with one endpoint in \(U\) and one in \(V(G)\setminus U\text{.}\)
Theorem 3.5.3. Edmonds’ Perfect Matching Polytope Theorem.
Let \(x=(x_{uv}: uv\in E(G))\) be a vector indexed by the edges of a graph \(G\text{.}\) The perfect matching polytope of \(G\) is equal to the set of all vectors \(x=(x_{uv}: uv\in E(G))\) satisfying the following constraints:
\begin{align*}
\sum_{v\in N(u)}x_{uv}=1 \amp \text{ for each }u\in V(G),\\
\sum_{uv\in \partial(U)}x_{uv} \geq 1 \amp \text{ for each }U\subseteq V(G) \text{ where }|U|\text{ is odd},\\
x\geq0.
\end{align*}
Theorem 3.5.4. Edmonds’ Matching Polytope Theorem.
Let \(x=(x_{uv}: uv\in E(G))\) be a vector indexed by the edges of a graph \(G\text{.}\) The matching polytope of \(G\) is equal to the set of all vectors \(x=(x_{uv}: uv\in E(G))\) satisfying the following constraints:
\begin{align*}
\sum_{v\in N(u)}x_{uv} \leq 1 \amp \text{ for each }u\in V(G),\\
\sum_{uv\in E(G): u,v\in U}x_{uv} \leq \frac{|U|-1}{2} \amp \text{ for each }U\subseteq V(G) \text{ where }|U|\text{ is odd},\\
x\geq0.
\end{align*}
Here are two YouTube videos related to this section:
