Motivation: A part of a proof for an alternative way to go around Tutte's and Hall's conditions.
Let $G$ be a connected bipartite graph with classes $(V_1, V_2)$ such that $|V_1| = |V_2|$ and $G$ satisfies Hall's condition both from $V_1$ to $V_2$ and from $V_2$ to $V_1$ (that is, for any $S \subset V_1$ we have $|\Gamma(S)| \geq |S|$ and for any $S \subset V_2$ we have $|\Gamma(S)| \geq |S|$, where $\Gamma(S)$ denotes the neighbourhood of $S$). Without using Hall's theorem or Tutte's theorem, show that $G$ satisfies Tutte's condition, that is, for any $S \subset V(G)$ the number of odd components of $G-S$ is at most the size of $S$.
I tried all kinds of inductions (on $|G|$, on $|S|$) but in both cases arguments like "remove a vertex/edge and use the induction hypothesis" break down.
Any help appreciated!
Let $Y_1,\ldots, Y_r$ be the odd-sized components of $G \setminus S$. Then for each $k$, the component $Y_k$ is such that $|Y_k \cap V_1| \not = |Y_k \cap V_2|$. Let $U_k$ be the larger of the two sets $Y_k \cap V_1$ and $Y_k \cap V_2$ and let $B_k$ be the smaller of the two sets $Y_k \cap V_1$ and $Y_k \cap V_2$. Then on the one hand note that $N_G(U_k) \subseteq B_k \cup S$ for each such $k$ [make sure you see why], and thus $\cup_{k=1}^r N_G(U_k) \subseteq S \cup (\cup_{k=1}^r B_k)$. However, on the other hand, note that $|B_k| < |U_k|$ [strict inequality]. So, note the following:
On the one hand, by assumption $|N_G(\cup_{k=1}^r U_k)| \ge $ $|\cup_{k=1}^r U_k|$, which is $\sum_{k=1}^r |U_k|$ because the $U_k$s are disjoint. So $S \cup (\cup_{k=1}^r B_k)$ must be at least $\sum_{k=1}^r |U_k|$.
On the other hand, $|S \cup (\cup_{k=1}^r B_k)|$ $\le$ $|S| +\sum_{k=1}^r |B_k|$ $\le |S| + (\sum_{k=1}^r |U_k|)-r$ [because $|U_k| > |B_k|$.
Can you finish from here.