Proof of a Corollary to Hall's Marriage Theorem 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!
 A: 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)|$.
A: 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)|$.
A: 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)|$
