G is a bipartite graph, where for every edge e=(a,b)[a,b are in A,B] d(a)>d(b), and d(a)>0, show that there is a matching saturating A

Question

I think the direction is definitely HALL, i tried using induction on the size of S, where S is some subgroup of A, but i wasn't able to complete the process.

Answer 1

One way to do this is the following:

First prove a lemma: If $G$ is a bipartite graph with bipartition $X,Y$ and no isolated vertices in $X$, such that $d(x)\geq d(y)$ whenever $x\in X$ and $y\in Y$ are adjacent. Then $|X|\leq|Y|$.

Then for each subset $S$ of $A$ you find that the degree conditions still hold for the subgraph induced by $S\cup N(S)$. Now the lemma implies that $|S|\leq|N(S)|$ and you have verified Hall's condition.

You can prove the lemma by induction on the maximum degree. Here are a few hints for the proof of the lemma.

Let $k$ be the maximum degree. The induction base ($k=1$) is simple. For the induction step, let $G$ be a smallest counterexample for the claim with maximum degree $k>1$. Let $P$ be the vertices in $X$ with degree $k$ and $Q$ the vertices in $Y$ with degree $k$.

Now prove following statements:

1. $P$ cannot be empty.

2. $Q$ cannot be empty.

3. All edges starting in $Q$ must go to $P$.

4. There is a matching of $Q$ in the subgraph induced by $P\cup Q$.

5. Removing the edges of this matching produces a smaller counterexample for the claim. This final contradiction shows that no such counterexample can exist.

Proof of item 2 (assuming we already proved that $P$ is not empty): Suppose $Q$ is empty. Now we remove one single edge $px$ that has an endpoint $p$ in $P$. The remaining graph still fulfills the degree conditions (the degree of the vertices in $Q$ can only be lower, the degree of the vertices in $P$ are unchanged, except the degree of $p$, that is now $k-1$, and because $Q$ was empty all neighbours of $p$ have degree at most $k-1$). But $X$ and $Y$ are still the same, so $G$ was not the smallest counterexample. Contradiction.