# Deficit version of Hall's theorem - help!

So I have the following two exam questions:

Let $G$ be a bipartite graph with vertex classes $A$ and $B$, where $|A|=|B|=n$. Suppose that $G$ has minimum degree at least $\frac{n}{2}$. By using Hall's theorem or otherwise, show that $G$ has a perfect matching. Determined (with justification) a vertex cover of minimum size.

Let G be a bipartite graph with vertex classes A and B, where $|A|=|B|=n$. Suppose that $k \in N$ and that $G$ has minimum degree at least $\frac{n-k}{2}$. Show that G has a matching of size at least $n-k$.

I think that first question amounts to proving that any k-regular bipartite graph satisfies Hall's condition and therefore contains a perfect matching, but I can't work out why the degrees are given. The second part looks like it should use the deficient version of Hall's theorem; if $N_G(S) \geq |S| - d$ the $G$ contains a matching of size $n-k$. However, I can't see how to find $N_G(S) \geq |S| - d$.

We start from the first question. In order to show that $$G$$ has a perfect matching we show that $$G$$ satisfies the conditions of Hall’s theorem. Indeed, let $$A’$$ be an arbitrary non-empty subset of $$A$$. If $$|A’|\le n/2$$ then pick any vertex $$v\in A’$$ and remark that $$|A'|\le n/2\le |N(v)|\le |N(A’)|$$. If $$|A’|> n/2$$ then $$A’$$ intersects $$N(u)$$ for each vertex $$u\in B$$, because both $$A’$$ and $$N(u)$$ are subsets of $$A$$, $$|A|=n$$, and $$|A’|+|N(u)|>n/2+n/2=n$$. Thus $$u\in N(A’)$$. Therefore $$N(A’)=B$$ and $$|A’|\le |A|=n=|B|=|N(A’)|$$.

Since $$G$$ is bipartite, each of sets $$A$$ and $$B$$ constitutes its vertex cover of size $$n$$. This value cannot be diminished, because $$G$$ has a perfect mathching of size $$n$$, so each subset consisting of less than $$n$$ vertices of $$G$$ would miss an edge of the matching.

We can reduce the second question to the first as follows. Add to each of classes $$A$$ and $$B$$ of $$G$$ $$k$$ new vertices adjacent to all of vertices of the other class. In such a way we create a bipartite graph $$G^*$$ with the vertex classes $$A^*$$ and $$B^*$$ of size $$n+k$$ each with minimum degree at least $$\frac {n-k}2+k=\frac {n+k}2$$. Therefore $$G^*$$ has a perfect mathching $$M^*$$, which has a size $$n+k$$. At most $$2k$$ edges of $$M$$ are incident to new vertices. When we remove these edges from $$M^*$$ we obtain a matching $$M$$ for $$G$$ of size at least $$n+k-2k=n-k$$.

• How is |A| less than or equal to n/2? May 19, 2017 at 14:37

By way of contradiction, suppose $G$ does not have a perfect matching. Because the minimum degree of each vertex is $n/2$ any $S\subseteq A$ with $\lvert S\rvert\le n/2$ must have $\lvert N(S)\rvert\ge n/2\ge\lvert S\rvert$. So there must at least one $S\subseteq A$ with $\lvert N(S)\rvert<\lvert S\rvert$ and $\lvert S\rvert>n/2$. Then observe that $B\setminus N(S)$ will be a collection of vertices whose neighborhood have less than $n/2$ vertices, implying that the average degree for each of these vertices is less than $n/2$, a contradiction.

The second part can be proved in a similar manner, I believe.

• Could you explain how to use this method in the second case please? Do you start by assuming that G has no matching of size > n-k ? Also I am a bit confused on how to change the inequalities. Oct 30, 2017 at 20:31
• The last paragraph of @Alex Ravsky answer is the way to do it. Does his description make sense to you? Oct 31, 2017 at 3:42