Matchings and Their Size
In a bipartite graph, edges connect vertices in two different parts. A matching selects some of those edges without using any vertex more than once. This makes a matching a way to pair distinct vertices across the two parts. The size of a matching measures how many pairs it makes; the matching number records the largest size available in the whole graph.
Throughout, graphs are finite and simple. A bipartite graph \(G=(V,E)\) has a bipartition \(X,Y\): the sets \(X\) and \(Y\) are disjoint, their union is \(V\), and every edge has one endpoint in each set. Either part may be empty. An isolated vertex is a vertex incident with no edge.
The empty set of edges is a matching of size \(0\), including when the graph has no edges. A particular matching and the matching number are not the same kind of object: \(M\) is a set of edges, while \(\nu(G)\) is a number. There may be several maximum matchings, and they need not saturate the same vertices.
Basic Facts About Matching Size
Proof. The edge set \(E\) is finite, so it has only finitely many subsets. The subsets that are matchings form a nonempty collection, because the empty set is a matching. Their sizes are therefore a nonempty finite set of integers, which has a largest element. A matching whose size is that largest element is a maximum matching, proving existence. Now let \(M\) have size \(k\). Each of its \(k\) edges has two distinct endpoints, and the definition of a matching says that endpoints of different edges are distinct. Thus \(M\) has \(2k\) distinct endpoints. These, and only these, are the vertices saturated by \(M\). \(\square\)
In a bipartite graph, every matching edge uses one vertex from \(X\) and one from \(Y\). Because matching edges do not share endpoints, a matching of size \(k\) uses \(k\) distinct vertices from each part. This gives a useful upper bound.
Proof. Each edge of \(M\) has exactly one endpoint in \(X\). Distinct edges of \(M\) have distinct endpoints, so these endpoints give \(|M|\) distinct vertices of \(X\). Hence \(|M|\leq |X|\). Counting the endpoints in \(Y\) gives \(|M|\leq |Y|\). Together, these inequalities give \(|M|\leq\min(|X|,|Y|)\) for every matching. A maximum matching is itself a matching, so the same bound holds for \(\nu(G)\). \(\square\)
The bound is a ceiling, not a guarantee that a matching of that size exists. The pattern of edges matters: vertices in one part may have too few distinct neighbors to be paired with all the vertices in the other part.
By the first proposition, a matching of size \(k\) saturates \(2k\) vertices. Therefore, a perfect matching in a graph of order \(n\) must have size \(n/2\), so \(n\) must be even. Conversely, if a matching has size \(n/2\), then it saturates \(2(n/2)=n\) distinct vertices. Since the graph has exactly \(n\) vertices, it saturates every vertex and is perfect. In a bipartite graph, a perfect matching also requires \(|X|=|Y|\), because it pairs every vertex of \(X\) with a distinct vertex of \(Y\), and vice versa.
Finding Matching Numbers in Small Graphs
Worked Example: A Matching Reaches the Part-Size Bound
Let \(G=(V,E)\) be bipartite with \(X=\{a,b,c\}\), \(Y=\{1,2\}\), \(V=X\cup Y\), and \(E=\{a1,a2,b1,b2,c2\}\). Consider \(M=\{a1,b2\}\).
The two selected edges have no common endpoint: \(a\neq b\) and \(1\neq2\). Thus \(M\) is a matching, and counting its edges gives \(|M|=2\). Its endpoints are \(a,b,1,2\), four distinct vertices; the saturation count agrees with \(2|M|=2\cdot2=4\). The vertex \(c\) is unsaturated.
For every matching, the part-size bound gives \(|M|\leq\min(|X|,|Y|)=\min(3,2)=2\). Since the displayed matching has size \(2\), the largest possible size is exactly \(\nu(G)=2\). This matching reaches the bound and saturates every vertex in the smaller part \(Y\), but it does not saturate all vertices of \(G\).
Check: Counting the two edges of \(M\) gives size \(2\); counting its four distinct endpoints gives \(4=2\cdot2\). The upper bound is \(2\), so the exhibited size cannot be improved.
Worked Example: The Part-Size Bound Need Not Be Reached
Let \(G=(V,E)\) be bipartite with \(X=\{a,b,c\}\), \(Y=\{1,2,3\}\), \(V=X\cup Y\), and \(E=\{a1,b1,c2,c3\}\). The part-size bound alone gives \(|M|\leq\min(3,3)=3\), but the edges impose a stronger restriction.
Take \(M_1=\{a1,c2\}\). These edges have distinct endpoints, so \(M_1\) is a matching of size \(|M_1|=2\). It saturates \(a,c,1,2\), which is four vertices, agreeing with \(2|M_1|=2\cdot2=4\). The vertices \(b\) and \(3\) are unsaturated.
No matching can have size \(3\). To have size \(3\), it would need to use all three vertices \(a,b,c\). But the only edge incident with \(a\) is \(a1\), and the only edge incident with \(b\) is \(b1\). Using both would use vertex \(1\) twice, which is forbidden in a matching. So at most one of \(a,b\) can be matched, and at most one further edge can use \(c\). Thus every matching has size at most \(2\). Since \(M_1\) has size \(2\), \(\nu(G)=2\), strictly less than the part-size bound \(3\).
There is another maximum matching \(M_2=\{b1,c3\}\). It also has two edges and four distinct endpoints, so it saturates \(b,c,1,3\). In particular, \(M_1\) and \(M_2\) are both maximum, but one leaves \(b\) unsaturated and the other leaves \(a\) unsaturated.
Check: For each displayed matching, the edge count is \(2\) and the number of distinct endpoints is \(4=2\cdot2\). The shared neighbor \(1\) prevents matching both \(a\) and \(b\), while the displayed matchings show that size \(2\) is attainable.
Worked Example: A Perfect Matching
Let \(G=(V,E)\) be bipartite with \(X=\{r,s,t\}\), \(Y=\{1,2,3\}\), \(V=X\cup Y\), and \(E=\{r1,r2,s2,s3,t1,t3\}\). The set \(M=\{r1,s2,t3\}\) is a matching: its three edges use distinct vertices on both sides.
Counting edges gives \(|M|=3\). Its endpoints are \(r,s,t,1,2,3\), so it saturates all six vertices; independently, the endpoint count is \(2|M|=2\cdot3=6\). Therefore \(M\) is perfect. The part-size bound gives \(|M|\leq\min(3,3)=3\), so \(\nu(G)=3\) and \(M\) is maximum.
There is no need to list every possible matching to establish the matching number: one matching of size \(3\) proves that \(\nu(G)\geq3\), and the part-size bound proves that \(\nu(G)\leq3\). Together they give equality.
Check: The selected edges \(r1,s2,t3\) have no repeated endpoints, and their three edges account for all three vertices of each part. Hence the matching is both perfect and of the largest possible size.
Reading What a Matching Tells You
When computing a matching, keep three objects separate: the matching itself, its size, and the set of vertices it saturates. For example, an edge set may have size \(2\), saturate four vertices, and leave other vertices unsaturated. The matching number is determined only after comparing the size of a proposed matching with an upper bound or another argument ruling out larger matchings.
For a bipartite graph, the part-size bound is often the quickest upper bound. If \(|X|=4\) and \(|Y|=2\), no matching can contain more than two edges, regardless of how many edges the graph has. But when the two parts have the same size, the bound may be loose, as the second example shows. There, the obstacle is not the total number of vertices in either part; it is that two vertices on one side compete for the same sole neighbor.
Isolated vertices are automatically unsaturated by every matching, because no matching edge can be incident with them. More generally, a vertex need not be saturated even by a maximum matching: the second example has maximum matchings that leave vertices on both sides unsaturated. Thus “maximum” means that no matching in the graph has greater size; it does not mean that every vertex is covered.
A Common Counting Mistake
Mistake: In the first example, the matching \(M=\{a1,b2\}\) has two edges, so it saturates two vertices. This confuses the number of selected edges with the number of their endpoints.
Correction: Each matching edge has two endpoints, and different matching edges have no endpoint in common. Therefore a matching of size \(2\) saturates \(2\cdot2=4\) vertices: \(a,b,1,2\). The number of edges is the matching's size; the number of saturated vertices is twice that size.
Another tempting error is to assume that equal part sizes force a perfect matching. They do not. In the second example, both parts have size \(3\), but no matching can use both \(a\) and \(b\), since both can only be paired with vertex \(1\). Always check the actual edge set as well as the sizes of the parts.
Check Your Understanding
For each question, distinguish the selected edges, the matching size, and the vertices saturated by that matching.
- In a bipartite graph with parts \(X=\{p,q,r,s\}\) and \(Y=\{1,2\}\), what is the largest size any matching can have? Justify the bound.
- Let \(X=\{a,b\}\), \(Y=\{1,2\}\), and \(E=\{a1,b1\}\). Find \(\nu(G)\), and identify the vertices saturated by each maximum matching.
- Prove directly from the definition that the empty matching saturates no vertices.
- A matching has size \(4\). How many vertices does it saturate? Explain why the answer does not depend on whether the graph is bipartite.
- Can a graph with an odd number of vertices have a perfect matching? Explain using the number of endpoints in a matching.