[proofplan]
For bipartite matching, we reduce a bipartite graph to a unit-capacity flow network whose integral flows encode matchings exactly. A polynomial-time maximum-flow algorithm then computes a maximum matching by reading off the middle arcs carrying one unit of flow. For three-dimensional matching, membership in NP follows from direct certificate checking, and NP-hardness follows by the identity reduction from the tripartite exact-cover-by-3-sets problem, which is NP-complete. The equivalence in the reduction is that $m$ disjoint triples in $X \times Y \times Z$, where $|X|=|Y|=|Z|=m$, necessarily cover every element of the three coordinate classes.
[/proofplan]
[step:Encode a bipartite matching instance as a unit-capacity flow network]
Let $G = (A \cup B,E)$ be a finite bipartite graph with $E \subset A \times B$. Define a directed network $N_G = (V_G,\mathcal{A}_G,c_G,s,t)$ as follows. The vertex set is
\begin{align*}
V_G := \{s,t\} \cup A \cup B,
\end{align*}
where $s$ and $t$ are two new vertices. The arc set is
\begin{align*}
\mathcal{A}_G := \{(s,a) : a \in A\} \cup \{(a,b) : (a,b) \in E\} \cup \{(b,t) : b \in B\}.
\end{align*}
The capacity function is the map $c_G: \mathcal{A}_G \to \mathbb{N}$ defined by $c_G(\alpha):=1$ for every arc $\alpha \in \mathcal{A}_G$.
A feasible flow on $N_G$ is a map
\begin{align*}
f: \mathcal{A}_G &\to [0,\infty)
\end{align*}
such that $0 \leq f(\alpha) \leq c_G(\alpha)$ for every $\alpha \in \mathcal{A}_G$ and such that flow conservation holds at every vertex $v \in V_G \setminus \{s,t\}$. Its value is
\begin{align*}
|f| := \sum_{a \in A} f(s,a).
\end{align*}
We use the standard polynomial-time maximum-flow theorem for integral capacities: a maximum flow in a finite directed network with integer capacities can be found in polynomial time and may be chosen integral, for instance by the Edmonds-Karp algorithm (citing a result not yet in the wiki: Edmonds-Karp polynomial-time maximum-flow theorem with integral capacities).
Since $N_G$ has $|A|+|B|+2$ vertices and $|A|+|B|+|E|$ arcs, constructing $N_G$ from $G$ has polynomial size and takes polynomial time.
[guided]
The purpose of the network is to force the matching constraints using capacity-one bottlenecks at the two sides of the bipartition. We introduce a source $s$, a sink $t$, and keep the original vertices $A \cup B$. The directed network $N_G = (V_G,\mathcal{A}_G,c_G,s,t)$ is defined by
\begin{align*}
V_G := \{s,t\} \cup A \cup B,
\end{align*}
with arcs
\begin{align*}
\mathcal{A}_G := \{(s,a) : a \in A\} \cup \{(a,b) : (a,b) \in E\} \cup \{(b,t) : b \in B\}.
\end{align*}
Every arc has capacity one, so the capacity function is the map $c_G: \mathcal{A}_G \to \mathbb{N}$ defined by $c_G(\alpha):=1$ for every arc $\alpha \in \mathcal{A}_G$.
A feasible flow is a map
\begin{align*}
f: \mathcal{A}_G &\to [0,\infty)
\end{align*}
with $0 \leq f(\alpha) \leq 1$ on every arc and with flow conservation at every vertex except $s$ and $t$. The value of the flow is
\begin{align*}
|f| := \sum_{a \in A} f(s,a).
\end{align*}
Why does this encode matchings? The arc $(s,a)$ can carry at most one unit, so a vertex $a \in A$ can be used at most once. Similarly, the arc $(b,t)$ can carry at most one unit, so a vertex $b \in B$ can be used at most once. The middle arcs $(a,b)$ are precisely the edges of the original graph, so any unit of flow through the middle selects an allowed edge.
To compute a maximum such flow, we use the standard polynomial-time maximum-flow theorem for integral capacities: a maximum flow in a finite directed network with integer capacities can be found in polynomial time and may be chosen integral, for instance by Edmonds-Karp (citing a result not yet in the wiki: Edmonds-Karp polynomial-time maximum-flow theorem with integral capacities). The hypotheses apply because $N_G$ is finite and every capacity is the integer $1$. The network has $|A|+|B|+2$ vertices and $|A|+|B|+|E|$ arcs, so both the construction and the maximum-flow computation have size polynomial in the input graph.
[/guided]
[/step]
[step:Identify integral flows with matchings of the same cardinality]
Let $f: \mathcal{A}_G \to \{0,1\}$ be an integral feasible flow on $N_G$. Define
\begin{align*}
M_f := \{(a,b) \in E : f(a,b)=1\}.
\end{align*}
For each $a \in A$, the capacity constraint on $(s,a)$ and flow conservation at $a$ imply
\begin{align*}
\sum_{\{b \in B : (a,b)\in E\}} f(a,b) = f(s,a) \leq 1.
\end{align*}
For each $b \in B$, the capacity constraint on $(b,t)$ and flow conservation at $b$ imply
\begin{align*}
\sum_{\{a \in A : (a,b)\in E\}} f(a,b) = f(b,t) \leq 1.
\end{align*}
Thus no two edges in $M_f$ share a vertex, so $M_f$ is a matching. Also, summing flow conservation over all vertices $a \in A$ gives
\begin{align*}
|M_f| = \sum_{(a,b)\in E} f(a,b) = \sum_{a\in A} f(s,a) = |f|.
\end{align*}
Conversely, let $M \subset E$ be a matching. Define a map $f_M: \mathcal{A}_G \to \{0,1\}$ as follows. For each $a \in A$, set $f_M(s,a):=1$ if $a$ is incident to an edge of $M$, and set $f_M(s,a):=0$ otherwise. For each edge $(a,b) \in E$, set $f_M(a,b):=1$ if $(a,b) \in M$, and set $f_M(a,b):=0$ otherwise. For each $b \in B$, set $f_M(b,t):=1$ if $b$ is incident to an edge of $M$, and set $f_M(b,t):=0$ otherwise.
Because $M$ is a matching, each vertex is incident to at most one edge of $M$, so $f_M$ satisfies the capacity constraints and flow conservation at every vertex in $A \cup B$. Hence $f_M$ is a feasible integral flow and
\begin{align*}
|f_M| = |M|.
\end{align*}
Therefore maximum-cardinality matchings in $G$ and maximum-value integral flows in $N_G$ have the same value, and a maximum matching is obtained by computing a maximum integral flow and selecting the middle arcs carrying one unit of flow. This proves that maximum bipartite matching is solvable in polynomial time.
[/step]
[step:Verify that three-dimensional matching belongs to NP]
An instance of Three-Dimensional Matching consists of finite sets $X,Y,Z$, a set $T \subset X \times Y \times Z$, and an integer $k \in \mathbb{N}$. A certificate is a finite list encoding a subset $M$ of triples. To verify the certificate, first check that every listed triple belongs to $T$, thereby confirming $M \subset T$. Then check that $|M| \geq k$ and, for every pair of distinct triples $(x,y,z),(x',y',z') \in M$, check that
\begin{align*}
x \neq x', \qquad y \neq y', \qquad z \neq z'.
\end{align*}
This pairwise check uses at most $|M|^2$ coordinate comparisons, and $|M| \leq |T|$. Hence certificate verification takes time polynomial in the input size. Therefore Three-Dimensional Matching is in NP.
[/step]
[step:Reduce tripartite exact cover by 3-sets to three-dimensional matching]
We use the following standard NP-complete problem: tripartite exact cover by 3-sets, whose input is a quadruple $(X,Y,Z,T)$ with $X,Y,Z$ finite pairwise disjoint sets satisfying $|X|=|Y|=|Z|=m$ and $T \subset X \times Y \times Z$, and whose question is whether there exists a subset $C \subset T$ with $|C|=m$ such that every element of $X \cup Y \cup Z$ appears in exactly one triple of $C$ (citing a result not yet in the wiki: NP-completeness of tripartite exact cover by 3-sets).
Define the reduction $R$ by sending the input quadruple $(X,Y,Z,T)$ to the Three-Dimensional Matching instance $(X,Y,Z,T,k)$, where $k := m$. This map only copies the finite sets and triples and adds the integer $m$, so it is computable in polynomial time.
If $(X,Y,Z,T)$ is a yes-instance of tripartite exact cover by 3-sets, then there is a subset $C \subset T$ with $|C|=m$ whose triples cover every element of $X \cup Y \cup Z$ exactly once. In particular, no two triples in $C$ share an $X$-, $Y$-, or $Z$-coordinate. Thus $C$ is a three-dimensional matching of size $k=m$.
Conversely, suppose that $(X,Y,Z,T,k)$ is a yes-instance of Three-Dimensional Matching with $k=m$. Then there exists $M \subset T$ with $|M| \geq m$ such that the triples in $M$ are pairwise disjoint in all coordinates. Since every triple in $M$ contains one element of $X$, and the $X$-coordinates of distinct triples in $M$ are distinct, we have $|M| \leq |X|=m$. Hence $|M|=m$. The same disjointness gives $m$ distinct elements of $Y$ and $m$ distinct elements of $Z$, so the triples in $M$ cover all of $X$, all of $Y$, and all of $Z$. Therefore $M$ is an exact cover of $X \cup Y \cup Z$.
The reduction preserves yes-instances and no-instances, and it is polynomial-time computable. Since tripartite exact cover by 3-sets is NP-complete, Three-Dimensional Matching is NP-hard.
[/step]
[step:Combine membership and hardness to obtain NP-completeness]
The previous step proves that Three-Dimensional Matching is NP-hard under polynomial-time many-one reductions. The membership step proves that Three-Dimensional Matching lies in NP. Therefore Three-Dimensional Matching is NP-complete. Together with the flow reduction for bipartite matching, this proves both assertions of the theorem.
[/step]
