Can anyone help me with this problem?
Let $G=(S,T;E)$ be a bipartite graph. Prove that $G$ has a spanning graph where every vertex from $S$ has degree k ($\in Z_+$) and every vertex from $T$ has degree at most 1, if and only if the following condition holds: $|N_G(A)| \geq k|A|, \forall A \subseteq S$.
I have tried to solved it, but with no results...
I found that on a k-regular bipartite graph with partitions A and B we have $k|A| = \sum deg(a) = |E| = \sum deg(b) = k|B|$ and if you think about it, it's pretty logical. So in my case I will have $\sum deg(a) = k|A|$ because all vertices from $S$ has the same degree. The $N_G(A)$ is the union of the neighbourhoods of the vertices. So the $|N_G(A)|$ is the sum of every connected vertice from the set $T$: $\sum 1, \forall t \in T$, where degree(t) = 1. But from this I can't show that the statement is true... And this is just in one direction... And I don't even know if this is correct...
Seeing that the condition is necessary is pretty straightforward: If there was a set $A \subseteq S$ with $|N_G(A)| < k |A|$ and $H$ a subgraph of $G$ in which every vertex in $a$ has degree $k$ then there must be $k|A|$ edges between $A$ and $N_G(A)$, so some vertex in $N_G(A)$ has degree $> 1$.
For the other direction I would propose building an auxiliary bipartite graph $G' = (S', T; E')$ where you replace every vertex in $S$ by $k$ copies. Then you can use Hall's theorem to get matching in $G'$ in which every vertex in $S'$ has degree 1. If you then contract back to $G$ you get a subgraph in which every vertex of $S$ has degree $k$ (one edge from each copy) and every vertex of $T$ still has at most degree 1.
Note that this subgraph will not necessarily be spanning (which would mean that every vertex of $T$ has degree exactly 1). This is generally impossible.