2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Brandon du Preez Jul 21 at 11:06
  • $\begingroup$ 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. $\endgroup$ – zhenwei zhai Jul 21 at 11:25
  • $\begingroup$ @zhenwei zhai, could you please clarify the definition of a pseudo k-regular bipartite graph? $\endgroup$ – kabenyuk Jul 21 at 13:42
  • 1
    $\begingroup$ I'm sorry the previous description was not clear,I have update the question. $\endgroup$ – zhenwei zhai Jul 21 at 14:49
1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – zhenwei zhai Jul 22 at 4:41
  • $\begingroup$ 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'$. $\endgroup$ – Mike Jul 22 at 15:14
  • $\begingroup$ 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)$. $\endgroup$ – Mike Jul 22 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.