5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 21, 2021 at 3:07

1 Answer 1

2
$\begingroup$

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$

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