1
$\begingroup$

Question: Let $G$ be a bipartite graph with vertex classes $A$ and $B$ with $|A| = |B| = n$ and $δ(G) = n/2 − 1$. Show that $G$ contains a matching which covers all but at most $2$ vertices in each vertex class.

My Answer: (adapted from Deficit version of Hall's theorem - help!)

Let $G$ be a bipartite graph with vertex classes $A$ and $B$ with $|A| = |B| = n$ and $δ(G) = n/2 − 1$. Also let $M$ be a matching in $G$.

Add $2$ new vertices to each of the classes $A$ and $B$ which are adjacent to all of the vertices of the other class, creating the graph $G'$. This graph has vertex classes $A'$ and $B'$ each of size $n+2$ and each with minimum degree at least $\frac{n-2}{2} + 2 = \frac{n+2}{2}$. So by Hall's Theorem $G'$ has a perfect matching $M'$, which has size at least $n+2$. At most 4 edges of $M$ are incident to the new vertices. When we remove these edges from $M'$ we obtain a matching $M$ for $G$ of size at least $n+2-4=n-2$, as required.

Where I am Confused: I know that if Hall's Theorem holds then the matching is perfect as $|A|=|B|$. But I am confused why Hall's Theorem holds for this new graph $G'$ and not sure how to show that it does.

$\endgroup$
1
$\begingroup$

Let $S$ be a subset of $A'$.

If $|S| \le \frac{n}{2}+1$, then clearly $|N_{G'}(S)| \ge \frac{n}{2} +1 \ge |S|$ since a single vertex of $S$ has at least $\frac{n}{2}+1$ neighbors.

Otherwise $|S| > \frac{n}{2}+1$. Then we claim $N_{G'}(S) = B'$, which would yield $|S| \le n+2 = |N_{G'}(S)|$. To verify this claim, note that if there existed some point of $B'$ not in $N_{G'}(S)$, then it must be connected to $\ge \frac{n}{2}+1$ points of $A'$, all not in $S$. But there are only $n + 2 - |S| < \frac{n}{2} + 1$ points of $A'$ not in $S$, a contradiction.

$\endgroup$

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.