$G - u - v$ is not matchable if and only if $G$ has a barrier $B$ such that $u, v \in B$.

Question

Question: Let $G$ be a matchable graph, and let $u$ and $v$ be distinct vertices of $G$. Show that $G - u - v$ is not matchable if and only if $G$ has a barrier $B$ such that $u, v \in B$.

My approach: Suppose that $G$ has a barrier $B$ such that $u,v \in B$. We will show that $G-u-v$ is not matchable. $G$ is matchable, implies that $c_{odd}(G-B) = |B|$. Let $B':=B-u-v$. Since $u,v\in B$, note that $G-B$ can be obtained by sequentially subtracting any permutation of $\{u,v,B'\}$ from $G$. This implies that $G-B = G-u-v-B'$. Hence, $c_{odd}(G-B) = c_{odd}(G-u-v-B')$. Let $H:=G-u-v$. Now $B'\subset B \subseteq V(G)$ and by definition $B'\cap \{u,v\}=\emptyset$, so $B'\subseteq V(G-u-v)=V(H)$. Then $|B| = c_{odd}(G-B) = c_{odd}(H-B')$. Since, $B'=B-u-v$, $|B'|=|B|-2\implies |B|=|B'|+2$. So, we have $$c_{odd}(H-B')=|B'|+2\implies c_{odd}(H-B')>|B'|.$$ Hence, by Tutte's theorem, $H=G-u-v$ is not matchable.

Now suppose that $G-u-v$ is not matchable. We will show that $G$ has a barrier $B$ such that $u,v \in B$. Let $H:=G-u-v$. Since $H$ is not matchable, by Tutte's Theorem there exists $S\subseteq V(H)$ such that $\mathrm{def} (S)>0$, that is, $c_{odd}(H-S)>|S|$. Now let $S':=S\cup\{u,v\}\subseteq V(G)$. Since $G$ is matchable, by Tutte's Theorem $c_{odd}(G-S')\le |S'|$. Note that $S\cap \{u,v\}=\emptyset$. This implies that $S=S'-u-v$, $|S|=|S'|-2$, and $$c_{odd}(G-S')=c_{odd}(G-u-v-S)=c_{odd}(H-S)>|S|=|S'|-2.$$ So, we have $|S'|-1\le c_{odd}(G-S')\le |S'|$, that is, either $c_{odd}(G-S')=|S'|$ or $c_{odd}(G-S')=|S'|-1$. If the former is true, then $S'$ is a barrier of $G$ (since $G$ is matchable) with $u,v\in S'$ (by definition), and we are done.

As one may note, I have already proved one direction of the statement in the question, but I am stuck with the other direction. In fact, given that $c_{odd}(G-S')=|S'|-1$, I am not able to construct a subset $S''\subseteq V(G)$ with $u,v\in S''$ such that $c_{odd}(G-S'')=|S''|$.

So, any hint along the above lines or any alternative ways of solving the problem would be appreciated. Thanks!

Answer 1

Nice work! You're almost there.

Hint:

Show that $c_{odd}(G - S')$ and $|S'|$ have the same parity.

Answer 2

Below is the remaining part of the proof.

So, we have $|S'|-1\le c_{odd}(G-S')\le |S'|$, that is, either $c_{odd}(G-S')=|S'|-1$ or $c_{odd}(G-S')=|S'|$. Suppose that the former is true. We know that for any graph $F$ and any proper subset $A$ of $V(F)$, we have $$c_{odd}(F-A)-|A|\equiv |V(F)|\pmod 2.$$ Now since $G$ is matchable, $|V(G)|$ is even, that is, $|V(G)|\equiv 0 \pmod 2$. So, for any proper subset $A$ of $V(G)$, we have $c_{odd}(G-A)-|A|\equiv 0 \pmod 2$. Now either $S'=V(G)$ or $S'\subset V(G)$. If the former is true then $c_{odd}(G-S') = 0$, and since $|V(G)|$ is even, $|S'|$ is also even. So, $c_{odd}(G-S')-|S'|=-|S'|\equiv 0 \pmod 2$. But we have $c_{odd}(G-S')-|S'|=-1\equiv 1 \pmod 2$. Contradiction! Now suppose that $S'\subset V(G)$. So, we must have $c_{odd}(G-S')-|S'| \equiv 0 \pmod 2$. But we have $c_{odd}(G-S')-|S'|=-1\equiv 1 \pmod 2$. Contradiction!

So, $c_{odd}(G-S')=|S'|$. Hence, $S'$ is a barrier of $G$ (since $G$ is matchable) with $u,v\in S'$ (by definition), and we are done.