As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$.

The general goal of the proof is to show that under these terms, the graph has a perfect matching (a subset of edges where all edges are disjoint in vertices, and the edges in said subset are reaching every vertex $v\in V$)

I wanted to use the proof of hall's marriage theorem, yet this requires that not only $|X|\leq |Y|$, but also that for every $S\subseteq X$, $|S|\leq |n(S)|$ where $n(S)$ is the group countaining neighbors of all vertices in $S$, which is the part I'm having a hard time proving.

I'm not sure how to explain that for every subset we choose $S\subseteq X$, the minimal size of $n(S)$ has to be $|S|$, which is due to the fact that every $v\in S$ has $k$ neighbors in $G$.

I've read about Konig's Theorem but I wasnt able to make the connection.


1 Answer 1


Suppose $S\subseteq X$. Then $n(S)\subseteq Y$.

Consider all edges with one endpoint in $S$.

Since there are $k$ edges that start with any particular point in $S$ and all these edges are different for points in $S$, the number of those edges is $k|S|$.

Similarly, the number of all edges with one endpoint in $n(S)$ is $k|n(S)|$.

Since each edge with one endpoint in $S$ is also an edge with one endpoint in $n(S)$, we have $$ k|S|\le k|n(S)|,$$ which means $$ |S| \le |n(S)|.$$

  • $\begingroup$ Thank you very much! $\endgroup$
    – Aishgadol
    Jan 19, 2023 at 9:16
  • $\begingroup$ You are welcome! $\endgroup$
    – John L.
    Jan 19, 2023 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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