Matchings in a bipartite graph. Augmenting path algorithm, Konig's theorem Hall's and Frobenius theorems. Existence of perfect matchings in regular bipartite graphs.

Matchings in Bipartite Graphs (!!!)

In a bipartite graph G(A, B, E), edges only exist between the two partitions A and B. Therefore matchings can only occur between the two partitions — no two vertices within the same partition can be matched. A perfect matching is one where every vertex in both partitions is matched.

M-Augmenting Path (!!!)

Given a bipartite graph G(A, B, E) and a matching M, an M-augmenting path is a path that: Starts at an unmatched vertex in A. Ends at an unmatched vertex in B. Alternates between edges not in M and edges in M. If an M-augmenting path exists, we can increase the size of the matching by swapping matched and unmatched edges along the path.

Augmenting Path Algorithm (!!!)

Input: A bipartite graph G(A, B, E) and a matching M. Output: Either an M-augmenting path, or if none exists, a minimum vertex cover. Let S = set of unmatched vertices in A, T = ∅. Take an unmarked vertex x ∈ S and process it: For each neighbor y of x not connected via a matching edge, add y to T. If y is unmatched, return the augmenting path. If y is matched to some z, add z to S. Mark x and repeat until all vertices in S are marked. If no augmenting path is found, return T ∪ (A \ S) as the minimum vertex cover.

Output Theorem of Augmenting Path Algorithm (!!!)

The set T ∪ (A \ S) returned by the algorithm (when no augmenting path exists) is a minimum vertex cover, and its size equals the size of the matching M. This means M is a maximum matching.

König's Theorem (!!!)

For any bipartite graph G: ν(G) = τ(G). For any bipartite graph G without isolated vertices: α(G) = ρ(G). In other words, in bipartite graphs the maximum matching equals the minimum vertex cover, and the maximum independent vertex set equals the minimum edge cover.

Hall's Theorem (!!!)

Given a loopless (not necessarily simple) bipartite graph G(A, B, E), there is a matching of A into B (all vertices of A are matched into B) if and only if for every S ⊆ A: |S| ≤ |N(S)|, where N(S) is the neighborhood of S in B. ( |S| ≤ |N(S)| )

Frobenius' Theorem (!!!)

A bipartite graph G(A, B, E) contains a perfect matching if and only if: |A| = |B|, and for every S ⊆ A, |S| ≤ |N(S)|, where N(S) is the neighborhood of S in B. In other words, Frobenius' theorem is Hall's theorem with the additional requirement that both partitions have equal size. ( |A| = |B| and |S| ≤ |N(S)| )

Perfect Matchings in Regular Bipartite Graphs (!!!)

Every k-regular (not necessarily simple) bipartite graph G(A, B, E) with k > 0 has a perfect matching. This follows from Frobenius' theorem: regularity forces |A| = |B| by double counting edges, and Hall's condition is satisfied since for any S ⊆ A, counting edges gives k|S| ≤ k|N(S)|, so |S| ≤ |N(S)|. ( d(v) = k for all v ∈ V(G)