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

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.

• The usual tool for this sort of problem is Hall's Marriage Theorem. I am not sure, but I suspect if this is true that's the thing to use. – Brandon du Preez Jul 21 at 11:06
• I know Hall's Marriage Theorem, and also have learned how to prove that the k-regular bipartite graph has a perfect match, but my knowledge of graph theory is weak, I did not find the answer to this question on the Internet, and I have been thinking about it for a long time, but I have not found a solution. – zhenwei zhai Jul 21 at 11:25
• @zhenwei zhai, could you please clarify the definition of a pseudo k-regular bipartite graph? – kabenyuk Jul 21 at 13:42
• I'm sorry the previous description was not clear，I have update the question. – zhenwei zhai Jul 21 at 14:49

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$$

• I don't quite understand Claim 0. In my opinion, if the degree of x in H′ is less than k, then the number of NH′(x) is less than the number of NH(x). So there is a situation where there is a edge in H and no connection in H', and claim 0 is not valid in my opinion. Could you please give me an example to explain claim 0 again? – zhenwei zhai Jul 22 at 4:41
• Sure. If there is a vertex $x\in X$ that has degree less than $k$ in $H'$, then one can use combinatorial reasoning to show that there is a vertex $y \in Y$ with degree less than $k$ in $H'$. By the fact that $H'$ is $k$-pseudoregular, $x$ and $y$ must form an edge in $H'$, otherwise the edge $xy$ could be added into $H'$. – Mike Jul 22 at 15:14
• So in the multigraph $H$ there is more than 1 edge between $x$ and $y$, whereas in $H'$ there is exactly 1 edge between $x$ and $y$. So $y$ is still in $N_{H'}(x)$ as it is in $N_H(x)$, it is that there is more than 1 edge between $x$ and $y$ in $H$, whereas there is exactly 1 edge between $x$ and $y$ in $H'$, that gives $d_H(x)>d_{H'}(x)$. – Mike Jul 22 at 15:26