[proofplan] We give an explicit deterministic polynomial-time decision algorithm. The algorithm maintains a matching $M$ and repeatedly searches for an augmenting path by breadth-first search in the directed alternating graph determined by $M$. Each successful augmentation increases $|M|$ by exactly one, and the absence of an augmenting path is proved to be equivalent to maximality of $M$ by analyzing the symmetric difference of two matchings. Since at most $\min\{|A|,|B|\}$ augmentations occur and each search is polynomial in the input size, the resulting decision procedure runs in polynomial time. [/proofplan] [step:Define the alternating search graph for a current matching] Let $G=(A \sqcup B,E)$ be a finite bipartite graph, where $A$ and $B$ are disjoint finite vertex sets and $E \subset A \times B$ is the edge set. Let $M \subset E$ be a matching, meaning that no two distinct edges of $M$ share a vertex. A vertex $v \in A \sqcup B$ is called $M$-free if no edge of $M$ is incident to $v$. Define the directed alternating graph associated to $M$ to be the directed graph $D_M = (A \sqcup B, F_M)$, where the directed edge set $F_M$ is obtained as follows: if $e=\{a,b\}\in E$ with $a\in A$ and $b\in B$, then $a \to b$ belongs to $F_M$ when $e \notin M$, and $b \to a$ belongs to $F_M$ when $e \in M$. A directed path in $D_M$ starting at an $M$-free vertex of $A$ and ending at an $M$-free vertex of $B$ is exactly an $M$-augmenting path in $G$: its edges alternate between edges outside $M$ and edges inside $M$, beginning and ending with edges outside $M$. [/step] [step:Find an augmenting path by breadth-first search] Let $S_M \subset A$ denote the set of $M$-free vertices in $A$, and let $T_M \subset B$ denote the set of $M$-free vertices in $B$. Run breadth-first search in $D_M$ with initial queue containing all vertices of $S_M$. If the search reaches a vertex of $T_M$, recover a directed path $P$ from some vertex of $S_M$ to some vertex of $T_M$ using the predecessor pointers maintained by breadth-first search. The graph $D_M$ has $|A|+|B|$ vertices and exactly $|E|$ directed edges, because each undirected edge of $G$ contributes exactly one directed edge to $D_M$. Implement $D_M$ by adjacency lists: for each edge $e=\{a,b\}\in E$, store either the arc $a\to b$ if $e\notin M$ or the arc $b\to a$ if $e\in M$. Breadth-first search keeps a queue, a visited mark, and one predecessor pointer for each vertex, so each vertex is enqueued at most once and each directed edge is inspected at most once. Hence this search and the path recovery take time polynomial in $|A|+|B|+|E|$. [/step] [step:Augment the matching by flipping along the path] Suppose breadth-first search returns an $M$-augmenting path $P$. Let $E(P) \subset E$ denote the set of undirected edges of $G$ occurring along $P$. Define the flipped edge set $M' = M \triangle E(P)$, where $\triangle$ denotes symmetric difference. Since $P$ alternates between edges outside $M$ and edges inside $M$, starts with an edge outside $M$, and ends with an edge outside $M$, the path contains exactly one more edge from $E(P)\setminus M$ than from $E(P)\cap M$. Therefore $|M'| = |M| + 1$. At each internal vertex of $P$, exactly one incident matched edge of $M$ is removed and exactly one incident previously unmatched edge is inserted. At each endpoint of $P$, no edge of $M$ was incident to that endpoint, and exactly one edge is inserted. Vertices not on $P$ are unaffected. Thus no vertex is incident to more than one edge of $M'$, so $M'$ is a matching. [/step] [step:Prove that absence of an augmenting path means the matching is maximum] We prove the contrapositive. Assume $M$ is not a maximum matching. Then there exists a matching $N \subset E$ with $|N|>|M|$. Consider the graph $H = (A \sqcup B, M \triangle N)$. Every vertex of $H$ has degree at most $2$, because it is incident to at most one edge of $M$ and at most one edge of $N$. Hence every connected component of $H$ is either a path, a cycle, or an isolated vertex, and the non-isolated components have edges alternating between $M$ and $N$. Cycles and even-length alternating paths contain equally many edges from $M$ and $N$. Since $|N|>|M|$, at least one connected component of $H$ contains more edges from $N$ than from $M$. Such a component must be an alternating path whose first and last edges belong to $N\setminus M$. Its two endpoints are not incident to any edge of $M$, because otherwise the alternating path could be extended by an edge of $M$. Since $G$ is bipartite with all edges between $A$ and $B$, this path has one endpoint in $A$ and one endpoint in $B$. Therefore it is an $M$-augmenting path. Thus, if no $M$-augmenting path exists, there is no matching larger than $M$, so $M$ is maximum. [guided] The key point is to justify the stopping rule. We must prove that failing to find an augmenting path is not merely a failure of the search procedure, but a certificate that the current matching is maximum. We prove the contrapositive. Suppose $M$ is not maximum. Then there is another matching $N \subset E$ satisfying $|N|>|M|$. Compare $M$ and $N$ only where they differ by forming the symmetric-difference graph $H = (A \sqcup B, M \triangle N)$. Here $M \triangle N$ consists of the edges that belong to exactly one of $M$ and $N$. Because $M$ is a matching, each vertex is incident to at most one edge of $M$. Because $N$ is also a matching, each vertex is incident to at most one edge of $N$. Therefore each vertex in $H$ has degree at most $2$. A finite graph whose vertices all have degree at most $2$ decomposes into isolated vertices, paths, and cycles. Moreover, along every non-isolated component, the edges must alternate between $M$ and $N$: two adjacent edges cannot both lie in $M$, and two adjacent edges cannot both lie in $N$, since either case would violate the matching condition at their shared vertex. Now count the contributions of each component to $|N|-|M|$. An alternating cycle has the same number of $M$-edges and $N$-edges. An alternating path whose first and last edges are of different types also has the same number of $M$-edges and $N$-edges. Since the total inequality $|N|>|M|$ holds, at least one component must contribute positively to $|N|-|M|$. Such a component must be an alternating path with one more $N$-edge than $M$-edge. Therefore its first and last edges both belong to $N\setminus M$. Let this path be denoted by $P$. Each endpoint of $P$ is incident to an edge of $N$ on the path. It cannot also be incident to an edge of $M$; if it were, that $M$-edge would belong to $M\triangle N$ unless it also belonged to $N$, and in either case the endpoint would not be an endpoint of the relevant alternating component. Hence both endpoints are $M$-free. Since $G$ is bipartite and every edge joins a vertex of $A$ to a vertex of $B$, a path with an odd number of edges has endpoints in opposite parts. The path $P$ has one more $N$-edge than $M$-edge, so it has odd length, and therefore its endpoints lie one in $A$ and one in $B$. Thus $P$ is an $M$-augmenting path: it starts at an $M$-free vertex in one bipartition class, ends at an $M$-free vertex in the other, and its edges alternate between edges outside $M$ and edges inside $M$. This proves the contrapositive. Consequently, if no augmenting path exists, then no larger matching exists, and $M$ is maximum. [/guided] [/step] [step:Bound the number of augmentations] Start with the empty matching $M_0=\varnothing$. After each augmentation, the matching size increases by exactly $1$. Every matching in $G=(A\sqcup B,E)$ has size at most $\min\{|A|,|B|\}$, since each edge of a matching uses one vertex of $A$ and one vertex of $B$, and no vertex is used twice. Therefore the algorithm performs at most $\min\{|A|,|B|\}$ augmentations. [/step] [step:Decide the language in polynomial time] On input $\langle G,k\rangle$, first verify in polynomial time that the input encodes a finite bipartite graph $G=(A\sqcup B,E)$ and an integer $k\in\mathbb{N}\cup\{0\}$. If the encoding is invalid, reject. If $k>\min\{|A|,|B|\}$, reject. Otherwise run the augmenting-path algorithm described above until either $|M|\ge k$ or no augmenting path exists. Each breadth-first search takes polynomial time in $|A|+|B|+|E|$, and there are at most $\min\{|A|,|B|\}$ searches that lead to augmentation, plus one final unsuccessful search. Hence the total running time is bounded by a polynomial in the input length. If the algorithm reaches $|M|\ge k$, then $G$ has a matching of size at least $k$, so it accepts. If the algorithm stops with no augmenting path and $|M|<k$, then the previous step shows that $M$ is maximum, so no matching of size at least $k$ exists, and the algorithm rejects. Thus $\mathrm{BIPARTITE\text{-}MATCHING}$ is decided by a deterministic polynomial-time algorithm, which proves $\mathrm{BIPARTITE\text{-}MATCHING} \in \mathrm{P}$. [/step]