Use Hall's Theorem to show if $|N(S)|\geq k|S|$ for all $\emptyset \neq S \subseteq A$, vertices of $G$ can be covered entirely by disjoint $k$-stars.

Question

Let $k \in \mathbb N$ with $k\ge2$. Consider a bipartite graph $G$ with vertex classes $A,B$, where $|B| = k|A|$.

Use Hall's Theorem applied to a suitable graph $G'$ to show that if $|N(S)|\geq k|S|$ for all $\emptyset \neq S \subseteq A$, then the vertices of $G$ can be covered entirely by disjoint $k$-stars. (A $k$-star is a tree with $k+1$ vertices and $k$ leaves.)

Answer 1

To obtain $G’$ from $G$ we clone $k$-times each vertex from $A$ (with its edges). Then the graph $G’$ satisfies the condition of Hall’s theorem, so it contains a perfect matching $M$. Joining the clones back (with its edges from $M$), we obtain a reqired partition.