04 Cycles, Travelling Salesman Problem, Metric TSP, Matching, Augmenting Paths, Hall's Marriage Theorem

Lecture from: 27.02.2025 | Video: Homelab

Recall

Hamiltonian Cycles and Eulerian Tours

Definitions

Let $G=(V,E)$ be a graph.

• Eulerian Tour: A closed walk in $G$ that traverses every edge exactly once.
• Hamiltonian Cycle: A cycle in $G$ that visits every vertex exactly once.

Eulerian Tours: Characterization

Theorem: A connected undirected graph $G=(V,E)$ contains an Eulerian tour if and only if the degree of every vertex in $G$ is even. Furthermore, such a tour can be found in $O(|E|)$ time.

This theorem provides a simple and efficient way to determine if an Eulerian tour exists and to construct one if it does. The condition on vertex degrees is both necessary and sufficient for the existence of an Eulerian tour in a connected graph.

Hamiltonian Cycles: Definition and Examples

A Hamiltonian cycle is a cycle that visits each vertex of a graph exactly once. Determining if a graph contains a Hamiltonian cycle is a much more complex problem than determining the existence of an Eulerian tour.

The Icosian Game and Sir William Hamilton

The concept of Hamiltonian cycles is historically linked to the “Icosian Game” invented by Sir William Rowan Hamilton. The game involved finding a Hamiltonian cycle on the vertices of a dodecahedron.

Examples

• Icosahedral Graph: The graph derived from the vertices and edges of an icosahedron does contain a Hamiltonian cycle.
• Petersen Graph: The Petersen graph, despite being highly symmetric and having degree 3 for every vertex, does not contain a Hamiltonian cycle. This illustrates that seemingly simple graphs can lack Hamiltonian cycles.
• Grid Graphs: An $n\times m$ grid graph contains a Hamiltonian cycle if and only if the product $n\times m$ is even (assuming $n,m\ge 2$). This can be proven using a chessboard coloring argument, as a Hamiltonian cycle in a bipartite graph must alternate between the two sets of vertices, requiring them to be of equal size.

Hamiltonian Cycles in Hypercubes: Gray Codes

Hamiltonian cycles have practical applications, for instance, in the design of rotary encoders using Gray codes.

Gray Codes and Hypercubes

An $n$-bit Gray code is a sequence of $2^n$ binary numbers such that each successive number differs in only one bit position. The existence of a Gray code of length $n$ is equivalent to the existence of a Hamiltonian cycle in an $n$-dimensional hypercube $H_n$.

Recursive Construction of Gray Codes

Hamiltonian cycles in hypercubes (and thus Gray codes) can be constructed recursively. For example, to construct a Gray code of dimension $d$, one can use two copies of a Gray code of dimension $d-1$, prefixing the first half with ‘0’ and the second (reversed) half with ‘1’.

Dirac’s Theorem: Sufficient Condition for Hamiltonian Cycles

Dirac’s Theorem: If a graph $G=(V,E)$ with $|V|=n\ge 3$ has a minimum degree $\delta (G)\ge \frac{|V|}{2}$, then $G$ contains a Hamiltonian cycle.

Dirac’s theorem provides a sufficient condition for the existence of a Hamiltonian cycle. It states that if a graph is “dense enough” (in terms of minimum degree), then it is guaranteed to be Hamiltonian.

Lemma for Dirac’s Theorem

Lemma 1: If a graph $G$ satisfies Dirac’s condition ($\delta (G)\ge n/2$), then for any $k$, $2\le k\le n$, either $G$ contains a cycle of length at least $k+1$, or $G$ contains a cycle of length at least $k$ that includes a given set of $k$ vertices.

This lemma is crucial in proving Dirac’s Theorem. It essentially shows that under Dirac’s condition, we can always find long cycles, eventually leading to a Hamiltonian cycle.

Complexity of Hamiltonian Cycle Problem

NP-Completeness

The problem of determining whether a graph contains a Hamiltonian cycle is NP-complete. This implies that it is unlikely to have a polynomial-time algorithm.

Theorem (Karp 1972): The Hamiltonian cycle problem is NP-complete.

Dynamic Programming Approach

While no polynomial-time algorithm is known, Hamiltonian cycles can be found using dynamic programming in $O(|V{|}^2\cdot 2^{|V|})$ time. This is a significant improvement over brute-force methods but is still exponential.

Dynamic Programming Algorithm Idea

The dynamic programming approach is based on computing $P_{S,x}$, which is 1 if there is a path starting at vertex 1, visiting exactly the vertices in set $S$, and ending at vertex $x$, and 0 otherwise. The recursion is defined based on extending paths by considering the last vertex visited before $x$.

Traveling Salesman Problem (TSP)

Definition

The Traveling Salesman Problem (TSP) is an optimization problem where, given a set of cities and the distances between each pair of cities, the goal is to find the shortest possible route that visits each city exactly once and returns to the starting city.

TSP is NP-Complete

The Traveling Salesman Problem is also NP-complete. This can be shown by reducing the Hamiltonian cycle problem to TSP.

Reduction from Hamiltonian Cycle to TSP

Given a graph $G=([n],E)$, we construct a complete graph $K_n$ and define edge lengths:

$l(\{x,y\})=\{\begin{array}{ll}0& \text{if }\{x,y\}\in E\\ 1& \text{otherwise}\end{array}$

$G$ has a Hamiltonian cycle if and only if the optimal TSP tour in $K_n$ with length function $l$ has a total length of 0.

Inapproximability of TSP

Unless P=NP, there is no polynomial-time $C$-approximation algorithm for the general TSP for any constant $C>0$. This means finding even an approximate solution within a constant factor of the optimal solution is also hard in general.

Metric Traveling Salesperson Problem: A Practical Approximation

While the general Traveling Salesperson Problem (TSP) is notoriously hard to solve optimally (NP-complete and even hard to approximate), a practically relevant special case arises when the distances between cities satisfy the triangle inequality. This special case is known as the Metric TSP, and it admits efficient approximation algorithms.

Triangle Inequality

In the Metric TSP, the distance function $l$ is required to satisfy the triangle inequality: for any three cities $x,y,z\in [n]$, the following holds:

$l(x,z)\le l(x,y)+l(y,z)$

This condition is quite natural in many real-world scenarios, such as road networks or Euclidean distances, where the direct path between two points is always no longer than any detour.

2-Approximation Algorithm for Metric TSP

For the Metric TSP, we can efficiently find a tour that is guaranteed to be no more than twice as long as the optimal tour. This is achieved using a clever 2-approximation algorithm based on Minimum Spanning Trees (MST).

Here are the steps of the 2-approximation algorithm:

1. Compute Minimum Spanning Tree (MST): Construct a Minimum Spanning Tree $T$ for the complete graph $K_n$ with edge weights given by the distance function $l$. Efficient algorithms like Kruskal’s or Prim’s algorithm can compute an MST in polynomial time.

   • Key Property: The total weight of the MST, $l(T)$, provides a lower bound on the length of the optimal TSP tour, $opt(K_n,l)$. This is because any TSP tour must span all vertices, and removing any edge from a tour yields a spanning path, which is no shorter than a spanning tree. Therefore, $l(T)\le opt(K_n,l)$.

2. Double the Edges: Create a multigraph $G^{\prime }$ by duplicating every edge in the MST $T$. In $G^{\prime }$, for every edge in $T$, there are now two parallel edges connecting the same vertices.

   • Why Doubling? Doubling the edges ensures that every vertex in $G^{\prime }$ has an even degree. Since $T$ is a tree, and we add each edge twice, the degree of each vertex in $G^{\prime }$ becomes twice its degree in $T$. If a vertex had degree $d$ in $T$, it will have degree $2d$ in $G^{\prime }$, which is always even.

3. Find an Eulerian Tour: Since every vertex in the multigraph $G^{\prime }$ has an even degree and $G^{\prime }$ is connected (because $T$ is a spanning tree), $G^{\prime }$ contains an Eulerian tour $W$. We can find such a tour efficiently using Hierholzer’s algorithm in time proportional to the number of edges in $G^{\prime }$, which is $O(|V|)$ since $T$ has $|V|-1$ edges.

   • Eulerian Tour Properties: An Eulerian tour traverses every edge of $G^{\prime }$ exactly once. The total length of the Eulerian tour $W$, $l(W)$, is simply twice the length of the MST, $2l(T)$, as we have doubled every edge. Therefore, $l(W)=2l(T)$. Combining this with the MST lower bound, we get $l(W)=2l(T)\le 2\cdot opt(K_n,l)$.

4. Shortcut the Eulerian Tour: Traverse the Eulerian tour $W$. As we traverse, create a new tour $C$ (Hamiltonian cycle) by “shortcutting” any vertex that has already been visited. Whenever we are about to visit a vertex $v$ that is already in $C$, we skip to the next unvisited vertex in $W$ that has not yet been added to $C$.

   • Why Shortcutting Works (Triangle Inequality): The triangle inequality guarantees that shortcutting does not increase the tour length. Suppose in the Eulerian tour we have a sequence of vertices … , $u,v_1,v_2,...,v_k,w,...$ where $u$ and $w$ are already in our Hamiltonian cycle $C$, and $v_1,v_2,...,v_k$ are vertices already visited in $C$ or are vertices we have already visited in this traversal of $W$ to construct $C$. Instead of going from $u$ to $v_1$, then $v_1$ to $v_2$, …, $v_k$ to $w$, we directly jump from $u$ to $w$. By the triangle inequality: $l(u,w)\le l(u,v_1)+l(v_1,v_2)+...+l(v_k,w)$. Therefore, shortcutting can only decrease or maintain the total tour length.

After shortcutting the Eulerian tour $W$, we obtain a Hamiltonian cycle $C$. The length of this cycle, $l(C)$, will be less than or equal to the length of the Eulerian tour $W$, due to the triangle inequality in the shortcutting step. Since $l(W)\le 2\cdot opt(K_n,l)$, we have:

$l(C)\le l(W)\le 2\cdot opt(K_n,l)$

This shows that the algorithm provides a 2-approximation for the Metric TSP, meaning the tour we find is at most twice as long as the optimal tour.

Matchings in Graphs: Finding Optimal Pairings

Matchings in graphs are fundamental structures in graph theory with wide applications, such as assignment problems, network flow, and combinatorial optimization. A matching represents a set of edges where no two edges share a vertex, effectively pairing up vertices in the graph.

Definitions: Types of Matchings

Let $G=(V,E)$ be a graph.

• Matching ($M$): A subset of edges $M\subseteq E$ such that no two edges in $M$ are incident to the same vertex. Formally, for any two distinct edges $e_1=\{u_1,v_1\}\in M$ and $e_2=\{u_2,v_2\}\in M$, we must have $\{u_1,v_1\}\cap \{u_2,v_2\}=\varnothing$.

• Vertex Covered by a Matching: A vertex $v\in V$ is said to be covered (or matched) by a matching $M$ if there exists an edge $e\in M$ that is incident to $v$.

• Perfect Matching: A matching $M$ is called a perfect matching if every vertex in $V$ is covered by $M$. A perfect matching pairs up all vertices in the graph. For a perfect matching to exist, the graph must have an even number of vertices, and $|M|=|V|/2$.

• Inclusion-Maximal Matching: A matching $M$ is inclusion-maximal if no more edges can be added to $M$ while still maintaining the matching property. In other words, for any edge $e\in E\setminus M$, $M\cup \{e\}$ is no longer a matching because $e$ would share a vertex with an edge already in $M$.

• Cardinality-Maximal Matching (Maximum Matching): A matching $M$ is cardinality-maximal (or simply maximum) if it has the largest possible number of edges among all possible matchings in $G$. There can be multiple maximum matchings in a graph. A maximum matching is always inclusion-maximal, but the converse is not necessarily true.

Greedy Algorithm for Inclusion-Maximal Matching

A simple and efficient way to find an inclusion-maximal matching is using a greedy approach.

GREEDY-MATCHING(G):

1. Initialization: Start with an empty matching $M=\varnothing$.
2. Iterate While Edges Exist: While there are still edges in the graph $E$: a. Select an Edge: Choose any arbitrary edge $e=\{u,v\}\in E$. b. Add to Matching: Include the chosen edge $e$ in the matching: $M\leftarrow M\cup \{e\}$. c. Remove Conflicting Edges: Remove the edge $e$ and all edges in $E$ that are incident to either vertex $u$ or vertex $v$. This ensures that no vertex is incident to more than one edge in $M$.
3. Return Matching: Once no more edges can be added, return the matching $M$.

Time Complexity: The greedy algorithm runs in $O(|E|)$ time. In each iteration of the while loop, at least one edge is added to $M$ and at least one edge is removed from $E$. The operations inside the loop (choosing an edge, adding to $M$, removing incident edges) can be performed efficiently.

Approximation Ratio: While the greedy algorithm finds an inclusion-maximal matching, it is not guaranteed to find a maximum matching. However, it provides a 2-approximation for the size of the maximum matching. Let $M_{Greedy}$ be the matching found by the greedy algorithm and $M_{max}$ be a maximum matching in $G$. Then, it is guaranteed that:

$|M_{Greedy}|\ge \frac{|M_{max}|}{2}$

Justification: Consider any edge $e_{max}=\{u,v\}$ in the maximum matching $M_{max}$. If we consider the edges in $M_{max}$ one by one, for each edge $e_{max}$, either $e_{max}$ is added to $M_{Greedy}$ or one of its endpoints, $u$ or $v$, must have been covered by an edge already in $M_{Greedy}$. This is because if neither $u$ nor $v$ was covered when we considered $e_{max}$, the greedy algorithm would have picked $e_{max}$ (or some edge that covers $u$ or $v$ at that point). Therefore, for every edge in $M_{max}$, at least one of its endpoints is covered by an edge in $M_{Greedy}$. Since each edge in $M_{Greedy}$ can cover at most two endpoints of edges in $M_{max}$, we get the 2-approximation ratio.

Augmenting Paths: Towards Maximum Matchings

To find a maximum matching (not just an inclusion-maximal one), we can use the concept of augmenting paths.

Definition of $M$-Augmenting Path

Given a matching $M$ in a graph $G$, an $M$-augmenting path $P$ is a simple path in $G$ with the following properties:

1. Alternating Path: The edges of $P$ alternately belong to the matching $M$ and not to the matching $M$. That is, if we traverse the path, the edges are in the sequence: not in $M$, in $M$, not in $M$, in $M$, … or in $M$, not in $M$, in $M$, not in $M$, …
2. Starts and Ends at Unmatched Vertices: Both endpoints of the path $P$ are unmatched vertices with respect to $M$. This means neither endpoint is incident to any edge in $M$.

Intuition Behind Augmenting Paths

Imagine you have a matching $M$ that is not maximum. This means there’s room to add more edges to the matching to increase its size. An augmenting path provides a systematic way to do this. Think of it as a “bottleneck” in your current matching.

An augmenting path is a path that starts and ends at vertices that are currently unmatched. It then cleverly alternates between edges that are in your current matching and edges that are not in your current matching.

When you find an augmenting path, you can “flip” the status of the edges along the path. Edges that were not in the matching become part of the matching, and edges that were in the matching are removed from the matching. This “flipping” action, known as augmentation, has a crucial effect: it increases the size of the matching by exactly one.

The reason the matching size increases is that an augmenting path always has one more edge outside the original matching than edges inside the original matching. Since it starts and ends with unmatched vertices and alternates edge types, a path of length $2k+1$ will have $k+1$ edges not in $M$ and $k$ edges in $M$.

The Symmetric Difference of Matchings: Visualizing Augmenting Paths

To understand why augmenting paths must exist if a matching is not maximum, consider two matchings: a non-maximum matching $M$ and a maximum matching $M^{\prime }$. Let’s examine their symmetric difference, denoted as $M\oplus M^{\prime }$.

The symmetric difference $M\oplus M^{\prime }$ is the set of edges that are in either $M$ or $M^{\prime }$, but not in both. In set notation: $M\oplus M^{\prime }=(M\cup M^{\prime })\setminus (M\cap M^{\prime })$.

Consider the subgraph formed by the edges in $M\oplus M^{\prime }$. Let’s analyze the properties of this subgraph:

1. Vertex Degree: In the subgraph formed by $M\oplus M^{\prime }$, each vertex has a degree of at most 2. This is because each vertex is incident to at most one edge in $M$ and at most one edge in $M^{\prime }$. Therefore, in the symmetric difference, the degree can be at most $1(fromM)+1(from{M}^{\prime })=2$.

2. Path and Cycle Decomposition: Since each vertex degree is at most 2, the connected components of the subgraph formed by $M\oplus M^{\prime }$ must be either paths or cycles.

3. Alternating Paths and Cycles: Because we are considering the symmetric difference of two matchings, every path and cycle in $M\oplus M^{\prime }$ will have edges that alternate between belonging to $M$ and $M^{\prime }$. Imagine traversing a path or cycle; you’ll see an edge from $M^{\prime }$, then one from $M$, then from $M^{\prime }$, and so on.

Now, let’s assume that the size of the maximum matching $M^{\prime }$ is strictly greater than the size of the non-maximum matching $M$, i.e., $|M^{\prime }|>|M|$. This means the symmetric difference $M\oplus M^{\prime }$ must contain more edges from $M^{\prime }$ than from $M$.

Consider the paths and cycles in the decomposition of $M\oplus M^{\prime }$. Since there are more edges from $M^{\prime }$ than from $M$ in total, there must be at least one connected component (either a path or a cycle) that contains more edges from $M^{\prime }$ than from $M$.

• Cycles: Cycles in $M\oplus M^{\prime }$ must have an equal number of edges from $M$ and $M^{\prime }$ (because they alternate). Therefore, cycles cannot contribute to an imbalance in edge counts between $M$ and $M^{\prime }$.

• Paths: For the total count of $M^{\prime }$ edges to exceed the count of $M$ edges in $M\oplus M^{\prime }$, there must exist at least one path component that has more edges from $M^{\prime }$ than from $M$. For an alternating path to have more $M^{\prime }$ edges, it must start and end with edges from $M^{\prime }$. Since the edges alternate, this means the path must start and end with edges from $M^{\prime }$ and therefore start and end at vertices that are matched by $M^{\prime }$ but not matched by $M$. But if they are not matched by $M$, and the path starts with an $M^{\prime }$ edge, and alternates, it means the start and end vertices of this path must be unmatched by $M$.

Therefore, if $|M^{\prime }|>|M|$, there must exist at least one path in $M\oplus M^{\prime }$ that starts and ends at vertices unmatched by $M$, and whose edges alternate between $M^{\prime }$ and $M$, starting and ending with edges from $M^{\prime }$. This path is precisely an $M$-augmenting path.

The symmetric difference $M\oplus M^{\prime }$ provides a conceptual tool. It decomposes into paths and cycles, and by analyzing these components, particularly in the case where $|M|<|M^{\prime }|$, we can logically deduce the existence of an $M$-augmenting path, which is the key to improving the matching $M$.

Berge’s Theorem: Characterizing Maximum Matchings

Berge’s Theorem provides a fundamental characterization of maximum matchings in terms of augmenting paths.

Theorem (Berge, 1957): A matching $M$ in a graph $G$ is a cardinality-maximal matching (maximum matching) if and only if there is no $M$-augmenting path in $G$.

This theorem is crucial because it gives us a way to check if a matching is maximum and a strategy to increase the size of a non-maximum matching if an augmenting path exists.

Augmenting Path Algorithm for Maximum Matching

Berge’s Theorem leads to a general algorithm for finding a maximum matching:

1. Start with Initial Matching: Begin with any matching $M$, for instance, an empty matching $M=\varnothing$ or a matching obtained by the greedy algorithm.
2. Search for Augmenting Path: Search for an $M$-augmenting path $P$ in $G$.
3. Check for Existence:
   • If no $M$-augmenting path exists: Then, by Berge’s Theorem, the current matching $M$ is a maximum matching. Return $M$.
   • If an $M$-augmenting path $P$ is found: Augment the matching. The operation to augment the matching is to take the symmetric difference of the matching $M$ and the edges of the augmenting path $P$: $M\leftarrow M\oplus P=(M\cup P)\setminus (M\cap P)$. This effectively “flips” the status of edges along the augmenting path: edges in $M\cap P$ are removed from the matching, and edges in $P\setminus M$ are added to the matching. This operation increases the size of the matching by exactly one, $|M\oplus P|=|M|+1$.
4. Repeat: Go back to step 2 with the augmented matching $M$.

This iterative process continues until no more augmenting paths can be found, at which point the matching is guaranteed to be maximum.

Finding Augmenting Paths and Time Complexity

The efficiency of the augmenting path algorithm depends on how efficiently we can search for an augmenting path in step 2.

• Bipartite Graphs: In bipartite graphs, augmenting paths can be found efficiently using Breadth-First Search (BFS). The time complexity to find an augmenting path in a bipartite graph is $O(|V|+|E|)$. Since the number of augmentations is at most $|V|/2$ (because the matching size increases by 1 in each augmentation and is bounded by $|V|/2$ for bipartite graphs), the overall time complexity for finding a maximum matching in a bipartite graph using augmenting paths and BFS is $O(|V|\cdot |E|)$.

• General Graphs: In general (non-bipartite) graphs, finding augmenting paths is more complex due to the possibility of odd cycles (“blossoms”). Edmonds’ Blossom algorithm is a more sophisticated algorithm to find augmenting paths in general graphs. It has a time complexity of $O(|V|\cdot |E|)$ per augmentation, leading to an overall complexity of $O(|V{|}^2\cdot |E|)$ or $O(\sqrt{|V|}\cdot |E|)$ with more refined implementations.

Hall’s Marriage Theorem: Existence of Perfect Matchings in Bipartite Graphs

Hall’s Marriage Theorem provides a necessary and sufficient condition for the existence of a matching that covers all vertices on one side of a bipartite graph.

Hall’s Condition

Let $G=(A\cup B,E)$ be a bipartite graph with bipartition $(A,B)$. Hall’s condition states that for every subset $X$ of $A$, the size of the neighborhood of $X$, $N(X)={\bigcup }_{x\in X}N(x)$, must be at least as large as the size of $X$:

$|X|\le |N(X)|\forall X\subseteq A$

Theorem Statement

Hall’s Marriage Theorem: Let $G=(A\cup B,E)$ be a bipartite graph with bipartition $(A,B)$. There exists a matching $M$ in $G$ that saturates $A$ (meaning every vertex in $A$ is matched by $M$, so $|M|=|A|$) if and only if Hall’s condition holds:

Hall’s Condition: For every subset $X$ of $A$, the size of the neighborhood of $X$, denoted as $N(X)={\bigcup }_{x\in X}N(x)$, must be greater than or equal to the size of $X$:

$|X|\le |N(X)|\forall X\subseteq A$

This theorem is fundamental in matching theory and has numerous applications. The “Marriage” analogy helps to understand the condition: imagine set $A$ as a set of men and set $B$ as a set of women, and an edge exists if a man and a woman are compatible. Hall’s Theorem tells us when it’s possible to marry off every man in $A$ to a compatible woman in $B$, ensuring no woman is married to more than one man.

Proof of Hall’s Marriage Theorem using Induction on $|A|$

We will prove Hall’s Marriage Theorem using induction on the size of set $A$, denoted by $a=|A|$.

Direction ($\Rightarrow$): Necessity of Hall’s Condition

First, we show that if a matching $M$ saturating $A$ exists, then Hall’s condition must hold. Assume there is a matching $M$ that saturates $A$. Consider any subset $X\subseteq A$. Let $M_X\subseteq M$ be the set of edges in $M$ that are incident to vertices in $X$. Since $M$ saturates $A$, for each vertex $x\in X$, there is a unique edge in $M_X$ incident to it. Let $Y\subseteq B$ be the set of vertices in $B$ that are matched to vertices in $X$ by $M_X$. Since $M$ is a matching, $|M_X|=|X|$. Furthermore, every vertex in $Y$ is a neighbor of some vertex in $X$, so $Y\subseteq N(X)$. Therefore, $|N(X)|\ge |Y|=|M_X|=|X|$, which shows that Hall’s condition holds.

Direction ($\Leftarrow$): Sufficiency of Hall’s Condition

Now, we need to prove the converse: if Hall’s condition holds, then there exists a matching that saturates $A$. We will use induction on $a=|A|$.

Base Case: $|A|=1$

Let $A=\{a\}$. Hall’s condition for $X=A=\{a\}$ requires $|\{a\}|\le |N(\{a\})|$, which simplifies to $1\le |N(a)|$. This means vertex $a$ must have at least one neighbor in $B$. If $N(a)$ is not empty, we can choose any neighbor $b\in N(a)$ and form a matching $M=\{\{a,b\}\}$. This matching saturates $A=\{a\}$, and the base case is established.

Inductive Hypothesis:

Assume that Hall’s Marriage Theorem holds for all bipartite graphs $G^{\prime }=(A^{\prime }\cup B^{\prime },E^{\prime })$ where $|A^{\prime }|\le a-1$. That is, if $|A^{\prime }|\le a-1$ and $G^{\prime }$ satisfies Hall’s condition with respect to $A^{\prime }$, then $G^{\prime }$ contains a matching that saturates $A^{\prime }$.

Inductive Step: Consider $|A|=a$

We need to show that if $G=(A\cup B,E)$ with $|A|=a$ satisfies Hall’s condition, then $G$ contains a matching that saturates $A$. We consider two exhaustive cases that cover all possibilities, based on the “tightness” of Hall’s condition for subsets of $A$.

Continue here: 05 Matchings in Bipartite Graphs