= Solution
Add $s$ adjacent to every vertex of $V_1$ and $t$ adjacent to every vertex of $V_2$. Suppose an $s$–$t$ separator $C$ has fewer than $n$ vertices. It cannot contain all of either class. Choose $x\in V_1\setminus C$ and $y\in V_2\setminus C$. No edge can join the remaining two classes, since it would give a three-edge $s$–$t$ path. Hence every neighbour of $x$ lies in $C\cap V_2$, and every neighbour of $y$ lies in $C\cap V_1$. The minimum-degree bound implies
$$
|C|\ge|C\cap V_1|+|C\cap V_2|\ge n/2+n/2=n,
$$
a contradiction. <Menger's theorem> therefore gives $n$ internally vertex-disjoint $s$–$t$ paths. Each uses at least one vertex of each original class, and only $n$ vertices are available in each class. Every path must consequently use exactly one of each. Their middle edges form \b[a <perfect matching>].
Back to article page
