0
$\begingroup$

I need help with this question.

Let G be a bipartite graph with bipartition $(A,B)$, such that $|A| = |B| = 10$, and every vertex of G has degree at least 5. Show that G has a perfect matching.

We are given the following hint : *Show that if X is a vertex cover of G then either $|X \cap A| \geq 5$ and $|X \cap B| \geq 5$, or $A \subseteq X$, or $B \subseteq X.$

This somehow relates to König's Theorem which states that in a bipartite graph G, the minimum size of a vertex cover in G is equal to the maximum size of a matching in G.

Thanks.

$\endgroup$
1
$\begingroup$

the hint clearly implies that $X$ must have $10$ vertices, which by König's theorem implies there is a matching with $10$ vertices.

So we just need to prove the hint. So suppose $X$ is a vertex cover that does not contain all of the vertices of $A$, we shall show that it contains at least $5$ vertices of $B$, this is obvious because any uncovered vertex in $A$ must have $5$ vertices in $B$, and all of these must belong to $X$. An analogous argument shows that if $X$ does not contain every vertex in $B$ it must contain at least $5$ vertices in $A$.

Conclusion: If $X$ does not contain $A$ and it does not contain $B$ it must contain at least $5$ vertices in each side.


We can also prove this using Hall's marriage theorem. Suppose that there is a subset $Y\subseteq A$ that has less than $|Y|$ neighbours. it follows that $|Y|$ is larger than $5$, but then every vertex in $B$ must have at least one vertex in $Y$, a contradiction, therefore halls condition holds and a matching that saturates $A$ exists.

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