Graph Matching

Introduction

A matching or independent edge set is a set of edges in a graph that share no common vertices. Graph matching algorithms are commonly used in competitive programming and can be broadly categorized into maximum matching and maximum weight matching. Since matching in bipartite graphs is equivalent to network flow problems, which have good properties and are relatively easier to handle, we will start by introducing both types of algorithms for bipartite graphs, then discuss algorithms for general graphs.

Graph Matching

Let \(G=(V,E)\) be an undirected graph, where \(V\) is the vertex set and \(E\) is the edge set. If a set of edges \(M\subseteq E\) contains no self-loops and no two edges share a common vertex, then \(M\) is called a matching or independent edge set of graph \(G\). An edge \(e\in E\) that appears in \(M\) is called a matched edge; otherwise, it is called an unmatched edge. Correspondingly, a vertex \(v\in V\) that is an endpoint of a matched edge is called a matched vertex; otherwise, it is called an unmatched vertex.

The size of a matching \(M\) is the number of edges it contains. For (weighted) undirected graph matching, the following concepts are often considered:

• Maximal matching: A matching to which no more edges can be added. A maximal matching is not necessarily a maximum matching.

  

• Maximum matching or maximum cardinality matching: A matching with the maximum number of matched edges. There may be more than one maximum matching, but the number of edges in a maximum matching is fixed and cannot exceed half the number of vertices in the graph.

  

• Maximum weight matching: In a weighted graph, the matching with the maximum sum of edge weights.

  

• Maximum weight maximum cardinality matching: Among all maximum matchings, the one with the maximum sum of edge weights.

  

• Perfect matching: A matching where every vertex is matched. A perfect matching is always a maximum matching. A complete graph with an even number of vertices always has a perfect matching.

• Near-perfect matching: A matching with exactly one unmatched vertex. This can only occur when the graph has an odd number of vertices. A near-perfect matching is also a maximum matching. A complete graph with an odd number of vertices always has a near-perfect matching.

In competitive programming, graph matching problems mainly refer to maximum matching or maximum weight matching.

Augmenting Path

In graph matching algorithms, augmenting paths are the core structure used to improve a matching.

Definition

For a graph \(G=(V,E)\) and one of its matchings \(M\), we can define the following two types of (simple) paths:

• An alternating path is a path consisting of alternating matched and unmatched edges.
• An augmenting path is an alternating path that starts and ends at unmatched vertices.

Since an augmenting path has one more unmatched edge than matched edges, the number of edges in an augmenting path must be odd. If we swap the matched and unmatched edges along an augmenting path, it remains an alternating path, and the size of the matching increases by \(1\). The process of finding an augmenting path and swapping its edges to increase the matching size is called augmentation. Mathematically, augmentation corresponds to taking the symmetric difference of the matching \(M\) and the augmenting path \(P\), resulting in a new matching \(M\oplus P\).

The figure below illustrates the process where the matching size increases from \(2\) to \(3\) after one augmentation operation.

Berge's Lemma

Berge's Lemma states that the method of improving a matching using augmenting paths is sufficient. That is, when no augmenting path can be found, the current matching is already a maximum matching.

Berge's Lemma

For a graph \(G=(V,E)\) and one of its matchings \(M\), \(M\) is a maximum matching if and only if there is no augmenting path relative to \(M\).

Proof

As explained earlier, if an augmenting path \(P\) exists, then \(M\oplus P\) is a larger matching than \(M\), so \(M\) cannot be a maximum matching.

Conversely, we need to show that if there exists a matching \(M'\) larger than \(M\), then there must exist an augmenting path \(P\) relative to \(M\). To do this, consider the symmetric difference \(M\oplus M'\). In the graph \((V,M\oplus M')\), the degree of each vertex can only be \(0\), \(1\), or \(2\); thus, each connected component of this graph must be a path, a cycle, or an isolated vertex. Moreover, the two edges incident to a vertex of degree \(2\) must come from different matchings, so in these cycles, the number of edges from \(M\) and \(M'\) is the same. Since \(M'\) is larger than \(M\), there exists at least one path where the number of edges from \(M'\) exceeds that from \(M\); denote this path as \(P\). Then, the start and end vertices of \(P\) are unmatched in \(M\), and \(P\) is an alternating path relative to \(M\), so \(P\) must be an augmenting path relative to \(M\). This completes the proof.

From this theorem, we derive the core idea for finding a maximum matching:

• Enumerate all unmatched vertices, search for augmenting paths, and continue until no augmenting path can be found.

In fact, after each augmentation, we do not need to traverse all unmatched vertices again. During the entire process of finding a maximum matching, each vertex only needs to be traversed once.

Proof

We only need to show that if, when enumerating vertex \(v\), there is no augmenting path starting from \(v\), then after several augmentations, there will still be no augmenting path starting from \(v\). This implies that even if augmentations change the matching, we do not need to recheck previously enumerated unmatched vertices.

Suppose otherwise. That is, assume \(v\) is an already enumerated unmatched vertex, and after augmenting along an augmenting path \(P\) from \(u\) to \(w\), a new augmenting path \(P'\) starting from \(v\) appears that did not exist before. Then, \(P'\) must share edges with \(P\); otherwise, augmenting along \(P\) would not change the matching status of edges in \(P'\), and \(P'\) would not be a new augmenting path created by this augmentation.

(In the figure, black edges are unmatched, red and blue edges represent different matching states.)

Let \(x\) be the first vertex on \(P\) reached from \(v\) along \(P'\). Since there existed an alternating path from \(v\) to \(x\) before the augmentation, \(x\) must be a matched vertex and cannot be \(u\) or \(w\). Therefore, on the augmenting path \(P\), the two edges incident to \(x\) have opposite matching states. This means that regardless of the matching state of the edge when arriving at \(x\) along the alternating path from \(v\), we can extend the alternating path along \(P\) to either \(u\) or \(w\). This implies that an augmenting path starting from \(v\) already existed before the augmentation, contradicting the assumption.

Alternating Tree

Another concept closely related to augmenting paths is the alternating tree. It is a tree generated during a DFS or BFS search for an augmenting path starting from an unmatched vertex \(r\).

For a graph \(G=(V,E)\) and one of its matchings \(M\), if a subgraph \(H\subseteq G\) is a tree rooted at an unmatched vertex \(r\), and every path connecting \(r\) to any \(v\in H\) is an alternating path, then \(H\) is called an alternating tree. Vertices at even depth in the tree are called even vertices, and those at odd depth are called odd vertices.

The figure below shows an alternating tree that might be obtained by performing BFS starting from unmatched vertex \(1\). (In the figure, red edges are matched, black edges are unmatched; dark vertices are matched, light vertices are unmatched.)

Existence of Perfect Matching

In graph matching theory, there are two important existence theorems that can be used to determine whether a perfect matching exists in a bipartite graph or a general graph.

Hall's Theorem

Assume \(G=(X,Y,E)\) is a bipartite graph with \(|X|\le |Y|\). For a matching \(M\) of \(G\), if all vertices in \(X\) are matched, then \(M\) is called an \(X\)-perfect matching, sometimes simply referred to as a perfect matching of the bipartite graph \(G\). This is the largest possible matching in a bipartite graph. Hall's Theorem provides a necessary and sufficient condition for the existence of such a matching.

Hall's Theorem states that as long as for any subset of \(X\), there are enough vertices in \(Y\) that can be matched to it, an \(X\)-perfect matching must exist.

Hall's Theorem

Assume \(G=(X,Y,E)\) is a bipartite graph with \(|X|\le |Y|\). For any \(W\subseteq X\), let \(N_G(W)\) denote the set of all vertices in \(G\) adjacent to at least one vertex in \(W\). Then, an \(X\)-perfect matching exists if and only if \(|W|\le |N_G(W)|\) holds for all \(W\subseteq X\).

Proof

The condition is clearly necessary. Suppose an \(X\)-perfect matching \(M\) exists. Then each vertex in \(X\) is matched to a distinct vertex in \(Y\). The set \(N_G(W)\) includes at least those vertices matched to vertices in \(W\), so its size is at least \(|W|\).

The condition is also sufficient. Suppose no \(X\)-perfect matching exists. Then there must be a maximum matching \(M\) such that some vertex \(v\in X\) remains unmatched. Let \(Z\) be the set of all vertices reachable from \(v\) via alternating paths, and let \(S=Z\cap X\), \(T=Z\cap Y\). The set \(S\setminus\{v\}\) must consist entirely of matched vertices; otherwise, an odd cycle would appear, contradicting that \(G\) is bipartite. The set \(T\) must also consist entirely of matched vertices; otherwise, an augmenting path would exist, contradicting that \(M\) is a maximum matching by Berge's Lemma. Since all are matched vertices and matching only occurs between \(X\) and \(Y\), the vertices in \(S\setminus\{v\}\) and \(T\) are in one-to-one correspondence, i.e., \(|T|=|S|-1\). Moreover, since vertices in \(T\) are already matched to vertices in \(S\), we have at least \(T\subseteq N_G(S)\); however, \(N_G(S)\) contains no unmatched vertex \(u\), because if \(u\) is adjacent to some \(v'\in S\), then extending the alternating path to \(v'\) would yield an alternating path to \(u\): this shows \(T=N_G(S)\). These arguments imply \(|N_G(S)|<|S|\), contradicting the condition of Hall's Theorem. Thus, an \(X\)-perfect matching must exist.

Corollary

Every regular bipartite graph has a perfect matching.

Proof

In a regular bipartite graph, all vertices have the same degree, say \(k\). First, verify that Hall's condition holds: for any \(W\subseteq X\), \(|N_G(W)|\ge |W|\). Since the number of edges incident to vertices in \(W\) is \(k|W|\), and each vertex in \(N_G(W)\) can be incident to at most \(k\) such edges, we must have \(k|W|\le k|N_G(W)|\), i.e., \(|W|\le |N_G(W)|\). In particular, \(|X|\le |Y|\); by symmetry, \(|X|=|Y|\). This means that in a regular bipartite graph, an \(X\)-perfect matching is also a perfect matching. Since Hall's Theorem guarantees the existence of an \(X\)-perfect matching, a perfect matching must also exist.

Tutte's Theorem

Tutte's Theorem provides a necessary and sufficient condition for the existence of a perfect matching in a general graph. This condition stems from a simple observation: a graph with an odd number of vertices cannot have a perfect matching.

Tutte's Theorem

A graph \(G=(V,E)\) has a perfect matching if and only if for every \(U\subseteq V\), \(\operatorname{odd}(G-U)\le |U|\), where \(G-U\) denotes the subgraph obtained by deleting vertices in \(U\) and their incident edges from \(G\), and \(\operatorname{odd}(G-U)\) denotes the number of connected components in \(G-U\) with an odd number of vertices.

Proof

It suffices to consider simple graphs, since multiple edges and self-loops do not affect the Tutte condition or the existence of a perfect matching.

The necessity of the condition is relatively easy. Suppose a perfect matching \(M\) exists. For any \(U\subseteq V\), after deleting vertices in \(U\) from \(G\), each odd component must have at least one vertex that cannot be matched within the same component; these vertices must seek matching with vertices in \(U\). For such matching to exist, we must have \(\operatorname{odd}(G-U)\le |U|\). This is the Tutte condition.

The sufficiency is more complex. Suppose \(G\) satisfies the Tutte condition but has no perfect matching. Since adding any edge to \(G\) would preserve the Tutte condition, we may assume \(G\) is a maximal such graph, i.e., \(G\) has no perfect matching, but adding any missing edge \(e\) to \(G\) yields a graph \(G+e\) that has a perfect matching. Let \(U\subseteq V\) be the set of all vertices with degree \(|V|-1\). It can be shown that every connected component of \(G-U\) is a complete graph. From this, we can construct a perfect matching for \(G\): first take a maximum matching in each connected component of \(G-U\), which leaves one unmatched vertex only if the component has an odd number of vertices; match these unmatched vertices to vertices in \(U\); since \(G\) has an even number of vertices (by taking \(U=\varnothing\) in the Tutte condition), the remaining unmatched vertices in \(U\) are even in number and can be paired up. This contradiction shows that no graph \(G\) satisfying the Tutte condition can lack a perfect matching.

The key is to prove that every connected component of \(G-U\) is a complete graph. Suppose not. Without loss of generality, let vertices \(x,y,z\) belong to such a component, with \((x,y)\in E\), \((y,z)\in E\), but \((x,z)\notin E\). Moreover, since \(y\notin U\), there must exist \(w\in V\setminus U\) such that \((y,w)\notin E\). By the maximality of \(G\), the graphs \(G+(x,z)\) and \(G+(y,w)\) have perfect matchings \(M_1\) and \(M_2\), respectively. Consider their symmetric difference \(M_1\oplus M_2\). Since in the graph \((V,M_1\oplus M_2)\) every vertex has degree either \(0\) or \(2\), \(M_1\oplus M_2\) is a disjoint union of even cycles, each alternating between edges from \(M_1\) and \(M_2\).

As shown in the figure, two cases arise:

• \((x,z)\) and \((y,w)\) lie in different cycles (left figure): Let \(C\) be the cycle containing \((y,w)\). Then \(M_2\oplus C\) is a perfect matching of \(G\).
• \((x,z)\) and \((y,w)\) lie in the same cycle (right figure): By symmetry, assume the cycle visits \(x,y,w,z\) in order. Take the path \(P\) from \(y\) to \(z\) via \(w\) on the cycle, and let \(C = \{(y,z)\}\cup P\). Then \(M_2\oplus C\) is also a perfect matching of \(G\).

In either case, we obtain a contradiction to the choice of \(G\). This contradiction shows that every connected component of \(G-U\) is a complete graph.

Corollary

Every bridgeless 3‑regular graph has a perfect matching.

Proof

To verify the Tutte condition, take any \(U\subseteq V\) and show \(\operatorname{odd}(G-U)\le |U|\). Let \(G_1,\dots,G_n\) be all odd components of \(G-U\). Let \(m_i\) be the number of edges connecting vertices in \(G_i\) to vertices in \(U\). A simple count gives

\[ 3|V(G_i)| = \sum_{v\in V(G_i)} d(v) = 2|E(G_i)| + m_i. \]

Thus, \(m_i\) must be odd. Since \(G\) has no bridges (cut edges), \(m_i\ge 3\). Therefore,

\[ \operatorname{odd}(G-U) = n \le \dfrac{1}{3}\sum_{i=1}^n m_i \le \dfrac{1}{3}\sum_{v\in U} d(v) = |U|. \]

Hence, the Tutte condition holds, and \(G\) must have a perfect matching.

Common Algorithms

A fundamental problem in combinatorial optimization is finding maximum matching and maximum weight matching in graphs.

Maximum Matching in Bipartite Graphs

See the Maximum Matching in Bipartite Graphs page.

In unweighted bipartite graphs, Kuhn's algorithm can solve it in \(O(|V||E|)\) time, and the Hopcroft–Karp algorithm can solve it in \(O(|V|^{1/2}|E|)\) time.

Maximum Weight Matching in Bipartite Graphs

See the Maximum Weight Matching in Bipartite Graphs page.

In weighted bipartite graphs, the Hungarian algorithm can be used. If Bellman–Ford is used for shortest path finding, the time complexity is \(O(|V|^2|E|)\); if Dijkstra's algorithm or Fibonacci heap is used, it can be solved in \(O(|V|^{2}\log {|V|}+|V||E|)\) time.

Maximum Matching in General Graphs

See the Maximum Matching in General Graphs page.

In unweighted general graphs, Edmonds' blossom algorithm can solve it in \(O(|V|^2|E|)\) time.

Maximum Weight Matching in General Graphs

See the Maximum Weight Matching in General Graphs page.

In weighted general graphs, Edmonds' blossom algorithm can solve it in \(O(|V|^2|E|)\) time.

Related Problems

Maximum (weight) matching is closely related to other graph theory problems. This section discusses only general graphs; for bipartite graphs, refer to the Maximum Matching in Bipartite Graphs page.

Maximum Weight Maximum Matching

The maximum weight maximum matching problem and the maximum weight matching problem can be reduced to each other. A notable difference is that maximum weight maximum matching may contain negative-weight edges, whereas maximum weight matching typically does not.

First, the maximum weight matching problem can be reduced to the maximum weight maximum matching problem. Set the weight of all negative-weight edges in graph \(G\) to \(0\); then, expand the graph into a complete graph \(G'\) by adding edges with weight \(0\). Note that in a complete graph with non‑negative edge weights, maximum weight maximum matching and maximum weight matching coincide. Thus, we only need to compute a maximum weight maximum matching \(M'\) of \(G'\), then remove all zero‑weight edges from \(M'\) to obtain an edge set \(M\), which is a maximum weight matching of \(G\).¹

Conversely, the maximum weight maximum matching problem can be reduced to the maximum weight matching problem. Simply add a sufficiently large positive constant \(K\) to all edge weights of \(G\) to obtain graph \(G'\). This ensures that a maximum weight matching of \(G'\) is also a maximum matching, hence a maximum weight maximum matching. This is because computing a maximum weight matching of \(G'\) is equivalent to maximizing over all matchings \(M\) of \(G\) the expression

\[ K|M| + \sum_{e\in M}w(e). \]

When \(K\) is sufficiently large, the gain \(K\) from matching one more edge outweighs any change in the sum of weights. Thus, the algorithm will first try to match as many edges as possible, then maximize the sum of weights. The constant \(K\) can be chosen as any value strictly larger than the difference between any two possible matchings. An obvious choice is

\[ K = \sum_{e\in E}|w(e)| + 1. \]

Minimum (Weight) Edge Cover

Another problem closely related to maximum (weight) matching is the minimum (weight) edge cover. The relationship between edge cover and matching (also called edge independent set) is analogous to that between vertex cover and independent set.

A set of edges \(C\subseteq E\) in a graph \(G=(V,E)\) is called an edge cover if every vertex \(v\in V\) is an endpoint of at least one edge in \(C\). When discussing edge covers, we always assume \(G\) has no isolated vertices.

For unweighted graphs, the minimum edge cover problem is almost equivalent to the maximum matching problem. For any maximum matching \(M\) of \(G\), adding one incident edge for each unmatched vertex yields a minimum edge cover \(C\). Their sizes satisfy the simple relation: \(|M|+|C|=|V|\). The figure below shows examples of minimum edge covers:

For weighted graphs, the minimum weight edge cover problem can be reduced to a minimum weight perfect matching problem. First, make a copy \(\tilde G=(\tilde V,\tilde E)\) of \(G=(V,E)\) with the same edge weights; then, connect each vertex \(v\in V\) to its copy \(\tilde v\in\tilde V\) with an edge whose weight is the minimum weight among all edges incident to \(v\) in \(G\). Denote the resulting graph as \(G'=(V',E')\). If \(G\) is bipartite or sparse, then \(G'\) is also bipartite or sparse, respectively. Moreover, the minimum weight edge cover problem for \(G\) reduces to the minimum weight perfect matching problem for \(G'\)²: from a minimum weight perfect matching \(M'\) of \(G'\), keep only edges from \(E\), and replace each matched edge \((v,v')\) with the minimum‑weight edge incident to \(v\) in \(G\), yielding a minimum weight edge cover of \(G\).

References

1. Wikiwand - Matching (graph theory)
2. Wikiwand - Blossom algorithm
3. 2015, "浅谈图的匹配算法及其应用" - Chen Yinbo
4. 演算法笔记 - Matching
5. the-tourist/algo
6. Bill Yang's Blog - 带花树学习笔记
7. 二分图的最大匹配、完美匹配和匈牙利算法
8. Wikiwand - Hopcroft–Karp algorithm
9. Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty. Graph theory with applications. Vol. 290. London: Macmillan, 1976.

---

1. Of course, this is not the only reduction method. For graph \(G=(V,E)\), one could also connect a copy \(\tilde G=(\tilde V,\tilde E)\) pointwise to the original graph, setting the weight of all newly added edges (including those in the copy) to \(0\), obtaining graph \(G'=(V',E')\). In other words, the vertex set of \(G'\) is \(V\cup V'\), and besides the edges of \(G\), every vertex \(v\in V\) is connected to its copy \(\tilde v\in V\) by a zero‑weight edge, and for every edge \((u,v)\in E\), \(\tilde u\) is connected to \(\tilde v\) by a zero‑weight edge. Every matching \(M\) of \(G\) corresponds to a perfect matching of \(G'\) with the same total weight: simply match each unmatched vertex \(v\) in \(G\) to its copy \(\tilde v\), and for each matched edge \((u,v)\), match \(\tilde u\) to \(\tilde v\). Therefore, a maximum weight maximum matching of \(G'\), i.e., a maximum weight perfect matching, restricted to \(E\), yields a maximum weight matching of \(G\). The advantage of this reduction is that if \(G\) is bipartite or sparse, then the expanded graph \(G'\) is also bipartite or sparse, respectively. ↩

2. For every perfect matching \(M'\) of \(G'\), we can obtain an edge cover \(C\) of \(G\) as described, with half the total weight; reversing this construction, for every edge cover \(C\) of \(G\), we can construct a perfect matching \(M'\) of \(G'\) with total weight at most twice that of \(C\). This shows the reduction is valid. ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用