# For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$

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.

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