Exercise 6.3 — Perfect matchings in regular bipartite graphs

For every finite type $V$ equipped with a finite enumeration, every simple undirected loopless graph $G$ on $V$ equipped with finite enumerations of all its neighbor sets, every pair of sets $L,R \subseteq V$, and every natural number $k$, assume that $L$ and $R$ are disjoint, every edge of $G$ has one endpoint in each part, $L \cup R=V$, $k>0$, and every vertex $v \in V$ has exactly $k$ distinct neighbors in $G$. Then there exists a subgraph $M$ of $G$ whose vertex set contains every vertex of $V$ and in which every vertex has exactly one neighbor. A subgraph chooses a vertex set and some of the edges of $G$, with both endpoints of every chosen edge in that vertex set; the conclusion therefore asserts a spanning matching, without asserting uniqueness of the subgraph. The degree used in the assumption is the natural-number cardinality of the finite set of neighbors, so it counts distinct adjacent vertices and involves neither an infinite cardinal nor any convention for the cardinality of an infinite set. The theorem excludes $k=0$ and excludes infinite vertex types, but it does not require $V$, $L$, or $R$ to be nonempty. When $V$ is empty, the degree condition is vacuous for every positive $k$, both parts are empty, and the empty subgraph satisfies the conclusion. If $V$ is nonempty and either part is empty, the bipartite assumptions force every degree to be zero, so the positive-degree hypotheses cannot all hold; likewise they cannot hold at an isolated vertex.