Prove the pseudo k-regular bipartite graphs has a perfect matching

Question

Suppose we have a bipartite graph $G=(X∪Y,E)$. It has the following properties：

• $|X| = |Y|$
• Maximum degree of vertices is $k$

I want to extend $G$ to a $k$-regular bipartite graph. So I write a loop to add edges to vertices whose degree is less than $k$. The loop only ends when there are no more edges to add. The filled bipartite graph obtained by the above loop may not be a $k$-regular bipartite graph but a bipartite graph with most vertices of degree $k$ and some vertices of degree less than $k$, and it is no longer possible to increase the degree of these vertices by adding edges.

So I call these filled bipartite graphs as the pseudo $k$-regular bipartite graphs. My question is that how to prove that the pseudo $k$-regular bipartite graph also has the perfect matching.

I found that this conclusion should be correct when I randomly disrupted the bipartite graph 10000 times by simulation, but I don't know how to prove it theoretically.

Answer 1

THM 1: A $k$-pseudoregular bipartite graph always has a perfect matching.

We now show this. Let $H'$ be a pseudo $k$-regular graph to start with.

TLDR: First we observe the following: There is a $k$-regular multigraph $H$, where there is an edge between 2 vertices in $H$ only if there is an edge between 2 vertices in $H'$. Then we use the fact that $H$ is a $k$-regular bipartite multigraph to observe via combinatorial reasoning that $|S| \le |N_H(S)|$ for all subsets $S$ of $X$. Then we see that $N_H(S) =N_{H'}(S)$, and so of course this implies that $|S| \le |N_{H'}(S)|$ as well. Then we see by Hall's there is a matching on $H'$ that saturates $X$ and so as $|X|=|Y|$ we also see that there is a perfect matching on $H'$.

---

To elaborate we first make the following observation:

Claim 0: You can always add edges to $H'$ until you get a $k$-regular bipartite multigraph $H$ that satisfies the following: if there is at an edge between $x$ and $y$ in $H$, then there is an edge between $x$ and $y$ in $H'$.

Indeed, let $y \in Y$ be a vertex of degree still less than $k$. Then there is a vertex $x \in X$ of degree less than $k$ [make sure you see why this is]. And furthermore, $xy$ form an edge in $H'$ otherwise $x$ and $y$ would have been connected in $H'$ already by the construction of $H'$. Add an edge between them.

We now note the following:

Claim 1: For each $S \subset X$, the inequality $|S| \le |N_H(S)|$ holds.

Indeed, we now present some notation. For each vertex $y' \in Y$ and any subset $U$ of $X$, let $d_U(y')$ be the number of edges in $H$ [the $k$-regular multigraph] of the form $y'x; x \in U$. Likewise, for each vertex $x' \in X$ and any subset $V$ of $Y$, let $d_V(x')$ be the number of edges in $H$ [the $k$-regular multigraph] of the form $yx'; y \in V$.

Then for each subset $S$ of $X$, note that on the one hand, $d_{N(H)}(x) = k$ for each $x \in S$. So the following equation holds: $$\sum_{x \in S} d_{N(H)}(x) = \sum_ {x \in S} k \ = \ k|S|.$$ However, $d_S(y) \le k$ for each $y \in N_H(S)$. So the following equation holds: $$\sum_{y \in N_H(S)} d_{S}(x) \le k |N_{H}(S)|.$$ However, [make sure you see that] the following also holds: $$\sum_{x \in S} d_{N(H)}(x) = \sum_{y \in N_H(S)} d_{S}(x).$$ [Indeed, both sides of the above count exactly the number of edges with one endpoint in $S$ and the other in $N_H(S)$.] So putting all these together gives $$k|S| \le k|N_H(S)|,$$ which, dividing both sides of the above by $k$, yields Claim 1. $\surd$

Claim 2: For each $S \subset X$, the inequality $|S| \le |N_{H'}(S)|$ holds.

Claim 2 follows from Claim 1, and the fact that there is an edge between $x$ and $y$ in $H$ only if there is an edge between $x$ and $y$ in $H'$. $\surd$

Finish the proof of THM 1 by Hall's Matching Thm, and noting that any matching that saturates $X$, must also saturate $Y$. $\surd$