Matching in Graphs: short notes (Engineering Mathematics)

Introduction

A matching pairs up vertices along edges so that no vertex is used twice: assigning workers to jobs they are qualified for, students to projects, or tasks to processors. The central questions are how large a matching can be, when every vertex can be matched, and how matchings relate to other covering problems (vertex covers, edge covers, independent sets). Bipartite matching is solvable in polynomial time and has exact min-max theorems; these are the results developed in the sections that follow.

Prerequisites

Graph Theory Fundamentals: bipartite graphs, degrees, paths, special graphs. Graphs are simple and undirected.

Core concepts

Definitions

Let $G = (V, E)$ with $n = |V|$ .

A matching $M \subseteq E$ is a set of edges, no two sharing an endpoint. A vertex incident to an edge of $M$ is matched (saturated); otherwise it is unmatched (exposed).
$M$ is maximal if no edge of $G$ can be added to it (every edge of $G$ touches a matched vertex).
$M$ is maximum if no matching of $G$ has more edges. Its size is the matching number $\nu(G)$ , also written $\alpha'(G)$ .
$M$ is perfect if every vertex is matched; then $|M| = n/2$ , so $n$ must be even.

Every maximum matching is maximal; a maximal matching need not be maximum. In the path $a - b - c - d$ , $\{bc\}$ is maximal (both other edges touch $b$ or $c$ ) but $\{ab, cd\}$ is larger and perfect.

Maximal versus maximum bound: if $M$ is maximal, then $|M| \ge \nu(G)/2$ . Each edge of a maximum matching has an endpoint matched by $M$ , and each edge of $M$ has only two endpoints. So the greedy algorithm (add any edge whose ends are both free) is within a factor 2.

Maximal, maximum and perfect matchings; Hall's condition — Figure 1. Top: one graph with a maximal matching of size 2 and a perfect matching of size 3. Bottom: a bipartite graph in which three left vertices have only two neighbours, so Hall's condition fails and no matching saturates the left side.

Matching numbers of standard graphs

Graph	$\nu(G)$	Perfect matching?
Path $P_n$ ( $n$ vertices)	$\lfloor n/2 \rfloor$	if and only if $n$ even
Cycle $C_n$	$\lfloor n/2 \rfloor$	if and only if $n$ even
Complete graph $K_n$	$\lfloor n/2 \rfloor$	if and only if $n$ even
$K_{r,s}$	$\min(r, s)$	if and only if $r = s$
Star $K_{1,s}$	1	only for $s = 1$
Hypercube $Q_k$ , $k \ge 1$	$2^{k-1}$	yes
Petersen graph	5	yes

Counting perfect matchings. $K_{2k}$ has $(2k-1)!! = (2k-1)(2k-3)\cdots 3 \cdot 1 = \dfrac{(2k)!}{2^k\, k!}$ perfect matchings (match the lowest-numbered free vertex to any of the remaining, repeat). $K_{k,k}$ has $k!$ (a perfect matching is a bijection between the sides). $C_{2k}$ has 2.

Augmenting paths and Berge's theorem

Given a matching $M$ , an $M$ -alternating path alternates between edges not in $M$ and edges in $M$ . An $M$ -augmenting path is an alternating path whose two ends are both unmatched. Swapping the edges along it (taking the symmetric difference $M \oplus P$ ) gives a matching with one more edge.

Berge's theorem: $M$ is a maximum matching if and only if there is no $M$ -augmenting path.

This yields the standard algorithm: start with any matching and repeatedly find an augmenting path. For bipartite graphs, each search is a BFS or DFS, giving $O(nm)$ time; the Hopcroft-Karp algorithm improves this to $O(m\sqrt{n})$ . Bipartite matching also reduces to maximum flow. General graphs need Edmonds' blossom algorithm, still polynomial.

Hall's marriage theorem

Let $G$ be bipartite with parts $X$ and $Y$ . For $S \subseteq X$ , let $N(S)$ be the set of vertices adjacent to some vertex of $S$ .

G \text{ has a matching saturating every vertex of } X \iff |N(S)| \ge |S| \text{ for every } S \subseteq X .

The condition is clearly necessary (the vertices of $S$ need distinct partners in $N(S)$ ); Hall's theorem says it is also sufficient. To show that no $X$ -saturating matching exists, exhibit one set $S$ with $|N(S)| < |S|$ (a Hall violator).

Corollaries.

If $|X| = |Y|$ and Hall's condition holds, the matching is perfect.
Every $k$ -regular bipartite graph with $k \ge 1$ has a perfect matching. (Counting edges: $k|S| \le k|N(S)|$ .) Repeating this, its edges split into $k$ perfect matchings.
Deficiency version: $\nu(G) = |X| - \max_{S \subseteq X}(|S| - |N(S)|)$ , where the maximum includes $S = \emptyset$ .

Covers and independent sets

Concept	Definition	Number
Independent set	vertices, no two adjacent	$\alpha(G)$ = maximum size
Vertex cover	vertices touching every edge	$\beta(G)$ (also $\tau(G)$ ) = minimum size
Matching	edges, no two sharing a vertex	$\nu(G)$ = maximum size
Edge cover	edges touching every vertex	$\rho(G)$ = minimum size (needs no isolated vertices)

Relations (for any graph $G$ on $n$ vertices):

$S$ is independent if and only if $V - S$ is a vertex cover, so $\alpha(G) + \beta(G) = n$ .
Gallai: if $G$ has no isolated vertices, $\nu(G) + \rho(G) = n$ .
$\nu(G) \le \beta(G)$ always (each matching edge needs its own cover vertex), and $\beta(G) \le 2\nu(G)$ (the ends of a maximal matching cover all edges).
Konig's theorem: if $G$ is bipartite, $\nu(G) = \beta(G)$ . This fails for odd cycles: $\nu(C_5) = 2$ but $\beta(C_5) = 3$ .
For bipartite $G$ without isolated vertices, combining the above, $\alpha(G) = \rho(G)$ .

Finding $\alpha$ or $\beta$ is NP-hard for general graphs, but polynomial for bipartite graphs by Konig's theorem.

Worked examples

Example 1: Hall violator

Bipartite graph with $X = \{x_1, x_2, x_3, x_4\}$ , $Y = \{y_1, y_2, y_3, y_4\}$ and edges $x_1y_1, x_1y_2, x_2y_1, x_3y_1, x_3y_2, x_4y_3, x_4y_4$ . For $S = \{x_1, x_2, x_3\}$ , $N(S) = \{y_1, y_2\}$ , so $|N(S)| = 2 < 3$ . No perfect matching exists. Deficiency $3 - 2 = 1$ is the largest, so $\nu = 4 - 1 = 3$ (for example $x_1y_2, x_2y_1, x_4y_3$ ).

Example 2: counting perfect matchings

$K_6$ : $5 \cdot 3 \cdot 1 = 15$ perfect matchings. $K_{4,4}$ : $4! = 24$ . $K_{3,4}$ : none (sides unequal), but $4 \cdot 3 \cdot 2 = 24$ matchings saturate the side of size 3.

Example 3: covers in a non-bipartite graph

For $C_7$ : $\nu = 3$ , $\beta = 4$ , $\alpha = 3$ , $\rho = 4$ . Checks: $\alpha + \beta = 7$ , $\nu + \rho = 7$ , and $\nu < \beta$ as for every odd cycle, whose maximum matching has $\lfloor n/2\rfloor$ edges and minimum vertex cover has $\lceil n/2\rceil$ vertices.

Example 4: augmenting path

In the path $a - b - c - d - e - f$ with $M = \{bc, de\}$ , the vertices $a$ and $f$ are unmatched, and $a - b - c - d - e - f$ alternates (non- $M$ , $M$ , non- $M$ , $M$ , non- $M$ ). Swapping gives $\{ab, cd, ef\}$ , a perfect matching.

Example 5: building a maximum matching by successive augmenting paths

Take the bipartite graph with parts $X = \{u_1, u_2, u_3\}$ and $Y = \{v_1, v_2, v_3\}$ and edges $u_1v_1$ , $u_1v_2$ , $u_2v_1$ , $u_2v_3$ , $u_3v_2$ , $u_3v_3$ .

Start with $M_0 = \{u_1v_1\}$ . The free vertices in $X$ are $u_2, u_3$ ; in $Y$ they are $v_2, v_3$ .

From free $u_2$ , the edge $u_2v_1$ reaches the matched vertex $v_1$ . Crossing the matching edge $v_1u_1$ and then the free edge $u_1v_2$ reaches free $v_2$ . So $u_2 - v_1 - u_1 - v_2$ is an $M_0$ -augmenting path. Symmetric difference gives $M_1 = \{u_2v_1, u_1v_2\}$ .
From free $u_3$ , the edge $u_3v_3$ reaches free $v_3$ , a length-1 augmenting path. Symmetric difference gives $M_2 = \{u_2v_1, u_1v_2, u_3v_3\}$ .

Now every vertex is matched, so $M_2$ is perfect and therefore maximum: $\nu = 3$ . By Berge's theorem there is no further augmenting path. An independent check: the three edges of $M_2$ form a matching, and a vertex cover of size 3 (for example $\{u_1, u_2, u_3\}$ , or $\{v_1, v_2, v_3\}$ ) proves $\beta \le 3$ ; with $\nu \le \beta$ always, both equal 3 (Konig).

The same $M_1$ also admits a longer augmenting path $u_3 - v_2 - u_1 - v_1 - u_2 - v_3$ , whose symmetric difference yields the different perfect matching $\{u_1v_1, u_3v_2, u_2v_3\}$ . Either route reaches size $\nu$ .

Example 6: Hall's condition and Konig's theorem on one graph

Reuse the bipartite graph of Example 1: parts $X = \{x_1, x_2, x_3, x_4\}$ , $Y = \{y_1, y_2, y_3, y_4\}$ , edges $x_1y_1$ , $x_1y_2$ , $x_2y_1$ , $x_3y_1$ , $x_3y_2$ , $x_4y_3$ , $x_4y_4$ .

Hall violator. For $S = \{x_1, x_2, x_3\}$ , $N(S) = \{y_1, y_2\}$ , so $|N(S)| = 2 < 3 = |S|$ . No matching saturates $X$ . The deficiency formula gives $\nu = |X| - \max(|S| - |N(S)|) = 4 - 1 = 3$ .
Explicit maximum matching. $M = \{x_1y_2, x_2y_1, x_4y_3\}$ has size 3. (The leftover unmatched pair is $x_3$ and $y_4$ ; no edge joins them, and every neighbour of $x_3$ is already matched.)
Konig certificate. The set $C = \{y_1, y_2, x_4\}$ is a vertex cover of size 3: every listed edge touches $y_1$ , $y_2$ or $x_4$ . So $\beta \le 3$ . Combined with $|M| = 3$ and $\nu \le \beta$ , one gets $\nu = \beta = 3$ . Konig's equality holds even though Hall's condition for an $X$ -saturating matching fails: the theorem equates matching number with cover number; it does not force a perfect matching.

Important properties and observations

A graph with an odd number of vertices has no perfect matching.
Removing a vertex set $S$ that leaves more than $|S|$ components with an odd number of vertices rules out a perfect matching (Tutte's condition, the general-graph analogue of Hall).
A tree has at most one perfect matching.
The size of any matching is at most the size of any vertex cover (weak duality); for bipartite graphs the two optima meet (strong duality, Konig).
Every maximal matching has size between $\nu/2$ and $\nu$ .

Standard confusions.

Maximal versus maximum. Maximal means no edge can be added; maximum means largest possible size. Every maximum matching is maximal, but not conversely (the path $a - b - c - d$ with $\{bc\}$ is the standard counterexample).
Perfect versus complete. A perfect matching saturates every vertex of $G$ . A matching that saturates every vertex of one part $X$ (but not necessarily of $Y$ ) is an $X$ -saturating matching, sometimes called a complete matching of $X$ into $Y$ . Perfect requires $|X| = |Y|$ as well.
Even order. A perfect matching needs an even number of vertices, because matched vertices come in pairs. An odd-order graph never has a perfect matching, no matter how dense its edges are. Completeness of the graph ( $K_n$ ) does not remove this obstruction when $n$ is odd: $\nu(K_n) = \lfloor n/2 \rfloor$ .

GATE examination perspective

Compute $\nu$ . For special graphs use the table; for small graphs find a matching and a vertex cover of the same size (in bipartite graphs) to prove optimality.
Hall's condition. Look for a set of left vertices with too few neighbours.
Counting perfect matchings. $(2k-1)!!$ for $K_{2k}$ , $k!$ for $K_{k,k}$ , 2 for an even cycle.
Covers. $\alpha+\beta=n$ ; $\nu+\rho=n$ without isolated vertices. The equality $\nu=\beta$ is guaranteed for bipartite graphs; some non-bipartite graphs also satisfy it, but not all.
Trap: maximal is not maximum.
Trap: applying Konig's theorem to a non-bipartite graph.
Augmenting-path construction. From any matching, search for an augmenting path; each success increases the size by one until Berge's condition holds.
Konig certificate. In a bipartite graph, a matching and a vertex cover of equal size prove both are optimal.

Summary

Matching: disjoint edges. Maximal: cannot be extended. Maximum: largest ( $\nu$ ). Perfect: covers all vertices.
Maximal $\ge \nu/2$ . Berge: maximum if and only if no augmenting path.
Hall: $X$ -saturating matching exists if and only if $|N(S)| \ge |S|$ for all $S \subseteq X$ .
$k$ -regular bipartite graphs ( $k \ge 1$ ) have perfect matchings.
$\alpha + \beta = n$ ; $\nu + \rho = n$ (no isolated vertices); bipartite: $\nu = \beta$ (Konig).
$K_{2k}$ : $(2k-1)!!$ perfect matchings; $K_{k,k}$ : $k!$ .
Build a maximum matching by repeated augmenting paths; stop when none remain (Berge).
Perfect needs even $n$ ; an $X$ -saturating matching is weaker than perfect when $|Y| > |X|$ .

Graph Theory Fundamentals: prerequisite. Bipartite graphs and special graphs.
Graph Colouring: related. Independent sets are colour classes; edge colourings are partitions into matchings.
Graph Connectivity: related. Menger's theorem and Konig's theorem are both min-max (flow) theorems.

Matching in Graphs

Introduction

Prerequisites

Core concepts

Definitions

Matching numbers of standard graphs

Augmenting paths and Berge's theorem

Hall's marriage theorem

Covers and independent sets

Worked examples

Example 1: Hall violator

Example 2: counting perfect matchings

Example 3: covers in a non-bipartite graph

Example 4: augmenting path

Example 5: building a maximum matching by successive augmenting paths

Example 6: Hall's condition and Konig's theorem on one graph

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Definitions

Matching numbers of standard graphs

Augmenting paths and Berge's theorem

Hall's marriage theorem

Covers and independent sets

Worked examples

Example 1: Hall violator

Example 2: counting perfect matchings

Example 3: covers in a non-bipartite graph

Example 4: augmenting path

Example 5: building a maximum matching by successive augmenting paths

Example 6: Hall's condition and Konig's theorem on one graph

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps