Prove that for a bipartite graph $G=(V,E)$ with $V = X \cup Y$, if for any subset $S \subseteq X$ we have $|\Gamma(S)| \geq \frac{|S|}{2}$, then there is a subgraph $H=(V,E^\prime)$ such that $d_H(x)=1$ for all $x \in X$ and $d_H(y) \leq 2$ for all $y \in Y$.
Here $\Gamma(S)$ is the set of neighbours of $S$, i.e. the union of neighbours of each $x$ in $S$.
I think it can be proven by induction. First, we observe that if $d(v) \leq 2$ for all $v \in Y$, then we can obtain the desired subgraph by throwing edges until every vertex in $X$ is degree of 1. The assumption assures that $d(x)$ is at least 1 for each $x\in X$. After that I assume that there is a vertex $y\in Y$ with $d(y) \geq 2$. I have tried couple more things after this as removing two vertices joining $y$ in X with minimum degree, etc. But it did not lead me anywhere. I would appreciate if you give me any hint!
Another attempt to solve the problem:
I read the proof of Hall's marriage theorem and tried to adopt this question to that proof.
So I want to check the following three cases:
If for every $S\subseteq X$, $|\Gamma(S)| \geq \frac{|S|}{2}+1$,
If there exists a subset $S$ of $X$ such that $|\Gamma(S)|=\frac{|S|}{2}$,
If there exists a subset $S \subset X$ such that $|\Gamma(S)|=\frac{|S|+1}{2}$.
I have proved that desired subgraph exists for the first and second cases but not for the third one. I would really really appreciate if you help me!
Here is my final answer if anyone is interested:
It is obvious that if $d(v) \leq 2$ for every $v \in Y$, then we can obtain the desired subgraph by throwing edges until every vertex $x$ in X is degree of 1. Therefore, in the rest of the proof we will assume that there exists a vertex $v \in Y$ with $d(v) >2$.
We will prove this question by induction on $|X|$. If $|X|=1$, let's say $X=\{x\}$, then $d(x)=|\Gamma(x)|\geq \frac{1}{2}$. Then just pick one of the neighbours of $X$ and consider that edge as the desired subgraph, so we are done. Now suppose for every subset $S \subseteq X$, $S \neq \emptyset,X$ we have $|\Gamma(S)| \geq \frac{|S|}{2}+1.$ Choose $x_1,x_2 \in X$ and $y \in Y$ such that $y \in \Gamma(x_1) \cap \Gamma(x_2)$ and $x_1$ and $x_2$ are the vertices with minimum degree among all $x \in X$ with $y \in \Gamma(x)$. This ensures that when we remove these vertices, there is no vertex in $X$ of degree 0. It is obvious from the assumption that we cannot have 3 vertices in $X$ with degree 1 and all are joined to the same vertex in $Y$. Once we remove these vertices, we obtain the induced graph $G_0 = G[V-\{x_1,x_2,y\}]$ with parts $X_1$ and $Y_1$ where $X_1=X-\{x_1,x_2\}$ and $Y_1=Y-\{y_1\}.$ For any $T \subseteq X_1$,
$\Gamma_{G_0}(T) = \Gamma_G(T)-\{y\}$ then $|\Gamma_{G_0}(T)| \geq |\Gamma_G(T)|-1 \geq \frac{|T|}{2}$.
So there is a subgraph $H_0$ of $G_0$ satisfying the desired conditions. Adding the vertices $x_1,x_2,y$ and the edges $x_1y,x_2y$ gives the desired subgraph in G.
Now suppose there exists $S \subseteq X$, $S \neq \emptyset , X$ with $|\Gamma(S)|= \frac{|S|}{2}$. Then let $X_1=S$ and $Y_1=N(S)$, and $X_2= X-X_1$ and $Y_2 = Y-Y_1$. Consider $G_1=G[X_1 \cup Y_1]$ and $G_2=G[X_2 \cup Y_2]$.
For any $T \subseteq X_1$, $\Gamma_{G_1}(T)=\Gamma_G(T)$ then $|\Gamma_{G_1}(T)|=|\Gamma_G(T)| \geq \frac{|T|}{2}$.
For any $T \subseteq X_2$, $\Gamma_{G_2}(T)=\Gamma_G(T) - N(S)= \Gamma_G(T \cup S) - N(S)$, then $|\Gamma_{G_2}(T)| \geq |\Gamma_G(T \cup S)|- |N(S)| \geq \frac{|T|+|S|}{2}-\frac{|S|}{2}= \frac{|T|}{2}$.
These prove that there are subgraphs in $G_1$ and $G_2$ with the desired conditions. Hence, their union gives the desired subgraph in $G$.
Finally, suppose if there exists $S \subseteq X$, $S \neq \emptyset , X$ with $|\Gamma(S)| = \frac{|S|+1}{2}$. Let $X_1=S$ and $Y_1=N(S)$, and $X_2= X-X_1$ and $Y_2 = Y-Y_1$ and consider $G_1=G[X_1 \cup Y_1]$ and $G_2=G[X_2 \cup Y_2]$. It is similar to the previous case to show that $G_1$ has a subgraph with desired conditions.
Now we obtain a new graph $G_2^\prime $ by adding vertices $u_1$ and $u_2$ to $X_2$ and $v$ to $Y_2$, respectively and edges $xv$ for every $x \in X_2$ as well as $u_1$ and $u_2$. Observe that $d(u_i)=1$ for $i=1,2$ and $y$ is contained in every neighbour set.
For any $T \subseteq X_2 \cup \{u_1,u_2\}$, $\Gamma_{G_2^\prime}(T) = \Gamma_G(T) \cup \{v\} - \Gamma(S) = \Gamma_G(T \cup S) \cup \{v\} - \Gamma(S)$. Then
$|\Gamma_{G_2^\prime}(T)| \geq |\Gamma(T \cup S) \cup \{v\}| - |\Gamma(S)| \geq \frac{|T|+|S|}{2}+1 - \frac{|S|+1}{2} \geq \frac{|T|}{2}.$
This shows that we have a subgraph in $G_2^\prime$ with desired conditions, and by removing $u_1,u_2$ and $v$ we obtain a subgraph in $G_2$ with desired conditions.
Similarly, the union of the subgraphs found in $G_1$ and $G_2$ is a subgraph in $G$ with the desired conditions.
This completes the proof.