Proof of a Corollary to Hall's Marriage Theorem

Question

I'm trying to prove Corollary 3.3 from this paper (http://www.sfu.ca/~mdevos/notes/graph/345_matchings.pdf) and am lost at the step that says: "Similarly, every vertex in N(X) has degree k, so t is less than or equal to k|N(X)|. It follows that |X| is at most |N(X)|."

How do we know that t is less than or equal to k|N(X)|?

Thanks so much!

Answer 1

On one side, we know that the $t$ edges we're counting are all the edges out of $X$, so there's $k|X|$ of them: $k$ for each vertex of $X$.

On the other side, we know that the $t$ edges we're counting all go to $N(X)$. But they might not be all the edges going to $N(X)$. If we were counting all the edges going to $N(X)$, there would be $k|N(X)|$ of them: $k$ for each vertex of $X$. But we might be missing some - there could also be edges to $N(X)$ from outside $X$. So all we have is an inequality $t \le k|N(X)|$.

Answer 2

We have from the paper $k|X| = t$ and $t \le k|N(X)|$, which, putting these together, gives us

$$k|X| = t; \ t \leq k|N(X)|$$

This in turn yields

$$k|X| = t \leq k|N(X)|$$

which gives

$$k|X| \leq k|N(X)|$$

which gives $|X| \le |N(X)|$.

**ETA per comment below: To see that $t =k|X|$, this follows because every vertex in $X$ has degreee $k$, and as every vertex in $X$ is on the same side of the bipartite graph, there is no edge incident to two vertices in $X$ i.e., for each $v$ let $E_v$ be the set of edges incident to $v$; then the $E_v$s; $v \in X$, are mutually disjoint and each $E_v$ has cardinality $k$. So $t = |\cup_{v \in X} E_v|$ $=\sum_{v \in X} |E_v| = k|X|$. Then Every one of the $t$ edges is incident to a vertex in $N(X)$. There are only $k |N(X)|$ edges total in $G$ that are incident to a vertex in $N(X)$ though, because each vertex in $N(X)$ has degree $k$. This gives $t \le k|N(X)|$.

Answer 3

Every vertex in $X$ has at least $k$-neighbors (that are all in $Y$ because the graph is bipartite

So if $|X| \le k$ we are done since $|N(X)| \ge k$

If $|X|=n>k$ then there is at least $n$ vertices in $N(X)$ since if there is less than $n$ vertices then you'll find a vertex in $N(X)$ of degree $> k$, a contradiction.

Thus, $|X| \le |N(X)|$