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$.
Best Answer
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$.