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 that you have read and understand our privacy policy and code of conduct.