The maximum matching of a bipartite graph $(S, T)$ is $|X|+\min\limits_{A \subseteq X} (\min\{0, |N_G(A)|-|A|\}$, where $X \in \{S, T\}$?

Question

Here is the full version of the problem I'm dealing with.

Let $G=(S,T;E)$ be a bipartite graph and let $X$ be one of the two classes of its bipartition (i.e., $X \in \{S,T\}$). For a subset $C \subseteq X$ we define: $$\sigma(C)=\min\{0, |N_G(C)|-|C|\},$$ where $N_G(C)$ is the neighbourhood of the subset $C$ in $G$) (note: $\sigma(\varnothing)=0$). We also define $\xi(S)=\min\limits_{A \subseteq S} \sigma(A)$ and $\xi(T)=\min\limits_{B \subseteq T} \sigma(B)$.
Prove that $$\nu(G)=|S|+\xi(S)=|T|+\xi(T),$$where $\nu(G)$ is the size of a maximum matching in $G$).

The case in which $G$ has a perfect matching is easy to prove, but I'm having trouble with how to approach the other cases.

Using Hall's theorem, I can prove one half of the equality at a time (i.e., either $\nu(G)=|S|+\xi(S)$ or $\nu(G)=|T|+\xi(T)$) but when it comes to proving the other one, I'm lost. I thought about modifying $G$ by adding additional nodes and edges until it has a perfect matching and then proving the property for this new graph, let's say $G'$, but I'm unsure as to how that translates to my main graph $G$.

Answer 1

You are on the right track. What you need is a nice way to construct $G'$ so that "the property for this new graph" can be translated to $G$ easily.

Here is my full proof.

---

Given the setup as in the question, let us prove $$\nu(G)=|S|+\xi(S).$$

• By definition of $\xi(S)$, there is some subset $C_0$ of $S$ such that $N_G(C_0)= |C_0| + \xi(S)$.

  • Any matching between $C_0$ and $T$ can have at most $N_G(C_0)$ edges.
  • Any matching between $S\setminus C_0$ and $T$ has at most $|S\setminus C_0| = |S| - |C_0|$ edges.

  Hence any matching between $S$ and $T$ has at most $N_G(C_0) + (|S| - |C_0|)= |S| +\xi(S)$ edges. That is, $\nu(G)\le |S| + \xi(S)$.

• Construct a new bipartite graph $G'=(S, T'; E')$, where $T'$ is $T$ with $-\xi(S)$ additional nodes and $E'$ is $E$ with $|S|\times (-\xi(S))$ additional edges that connect every node in $S$ with every additional node.
  We can check that $G'$ satisfies Hall's condition, that is, for every subset $C\subseteq S$, we have $N_{G'}(C)\ge |C|$.
  Hence there is $m'$, a matching of $G'$ that matches each node in $S$ with a node in $T'$.
  Remove the edges in $m'$ that end at additions nodes, we obtain a matching of $G$, which has $|S| - |{-}\xi(S)| = |S| + \xi(S)$ edges since $-\xi(S)$ edges are removed.
  So, $\nu(G) \ge |S|+\xi(S)$.

---

Switching $S$ and $T$, we obtain $$\nu(G)=|T|+\xi(T).$$ $\checkmark$