Vertices of $G$ covered entirely by disjoint $k$-stars

Question

Let $k \in \mathbb{N}$ with $k \geq 2$, and consider a bipartite graph with vertex classes $A,B$ such that $\mid B \mid = k\mid A \mid$. Using Hall's theorem on a suitable graph $G'$, show that if $ \mid N(S)\mid \geq k\mid S \mid$ for all $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

Consider the bipartite graph $G'$ with vertex classes $A$ and $C=\{U\subset B:|U|=k\}$. A vertex $a\in A$ is connected in $G'$ to a vertex $c\in C$ iff $a$ is connected to all $b \in c$ in $G$. Now, since for every $\varnothing\neq S\subseteq A$, $|N_G(S)|\geq k|S|$, then $|N_{G'}(S)|\geq{k|S| \choose k}\geq|S|$. Therefore, there is a matching in $G'$ that covers $A$. Construct a $k$-star covering by connecting each element of $A$ in $G$ to all the elements of the subset that matched that element in $G'$.