I am trying to prove the following claim.

Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$. Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), where $C_s$ and $C_t$ are the connected components of $G-S$ containing vertices $s$ and $t$ respectively. Suppose that $x \in C_s$, and let $y\in C_t$. Let $G'$ be the graph that results from $G$ by adding the edge $(y,t)$. Then there is a minimum $st$-separator $T'$ in $G'$ that contains $x$ (i.e., $x\in T'$).

The claim clearly holds if the vertex-connectivity of $G'$ is greater than the vertex-connectivity of $G$, because the connectivity can grow by at most one. I cannot prove that this holds in the case where the connectivity of $G$ and $G'$ is the same.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.