1
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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

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

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Koala
    Oct 30, 2017 at 20:31
  • $\begingroup$ The last paragraph of @Alex Ravsky answer is the way to do it. Does his description make sense to you? $\endgroup$ Oct 31, 2017 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.