# 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\}$?

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

• Could you make your title be a shorter summary, and put the specific question in the body of your post? A title is not intended to state the full question -- just something to help people get a sense of what to expect. Also using Latex in the title may often not be the best idea. See also cs.meta.stackexchange.com/a/815/755.
– D.W.
Dec 21, 2021 at 3:07

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