G a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$.

Question

Let $k \geq 1$ be an integer, and let G be a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$.

I have managed to prove this claim in the case where $|A| = |B| = 2k$, but can't extend it to the more general case where $|A|\geq|B| \geq 2k$.

Here's my logic:

I use Hall's theorem to show the case $|A| = |B| = 2k$. It suffices to show that for any $Y \subseteq A$, $|N(Y)| \geq |Y|$, where $N(Y)$ denotes the neighbourhood of $Y$. If $|Y|\leq k$, this is clear, since for any $v \in Y$, $\deg_B (v) \geq k$, as $G$ is k-connected. Otherwise, $|Y| > k$ and we suppose, by way of contradiction that $|N(Y)| < |Y|$. Then, $|N_{A \setminus Y} (N_B (Y ))|< k$, so there exist less than $k$ paths from any $v\in Y$ to $u \in A \setminus Y$, which contradicts $G$ being k-connected.

First of all, does this seem correct? Second, is this a good start, or it's unnecessary and theres a quicker way to prove the claim. Third, how would one extend this to the general case?

Answer 1

Hints: Let $G = (A,B)$ be our bipartite graph.

Piggybacking off @Misha's comment of using Koing's theorem, we want to show that every vertex cover has size at least $2k$. Suppose not. Let $V_c \subseteq V(G)$ be a vertex cover and suppose $|V_c| < 2k$. Then there exist a vertex $a \in A$ such that $a \notin V_c$. Choose another vertex $a' \in A$ and notice that $a$ and $a'$ are not adjacent.

Hence, by Menger's theorem, there exists $k$-internally disjoint paths between $a$ and $a'$, and for convenience let's orient them such that the paths point from $a'$ to $a$. (Another hint: what can you say about the second last vertex of this path?).

Now, as $a \notin V_c$, observe that the second last vertex of the graph is in $B$, and must be in $V_c$. More specifically, if the path is $a' \to v_1 \to v_2 \to \dots \to v_n \to a$, then $v_n \in B$ and $v_n \in V_c$. For each internally disjoint path, we get such a $v_n \in B \cap V_c$, and there are no duplicates. Thus, $|B \cap V_c| \geq k$.

A similar argument shows that we can choose a vertex $b \in B$ and $b \notin V_c$ and similarly conclude that $|A \cap V_c| \geq k$. This gives the desired contradiction since $|V_c| \geq 2k$.

Remark: this proof doesn't say the stronger statement that $|A \cap V_c| \geq k$ and $|B \cap V_c| \geq k$. This is false, counterexamples are easy to construct.