Proving a property of minimal st-separators that are not minimum st-separators

Let $$G$$ be an undirected, connected graph, and $$s,t$$ non-adjacent vertices in $$G$$. Denote by $$k_{st}(G)$$ the $$st$$-connectivity of $$G$$. That is, $$k_{st}(G)$$ is the size of any minimum $$st$$-separator of $$G$$.

(*) It can be shown that if a vertex $$v$$ belongs to any minimum $$st$$-separator of $$G$$, then $$k_{st}(G-v)=k_{st}(G)-1$$.

How do you prove the following: Let $$S$$ be a minimal $$st$$-separator of $$G$$ that is not a minimum $$st$$-separator of $$G$$. Prove that $$S$$ contains at least one vertex $$v\in S$$ such that $$k_{st}(G-v)=k_{st}(G)$$.

It seems very intuitive that this would hold, especially since (*) can be shown. However, I have yet to find a formal proof...

1 Answer

It does not hold, as can be seen from the red separator in this example.

Furthermore, a vertex in a minimum separator can be separated from $$s$$ and $$t$$ by a minimal separator:

• Thank you for the reply! Here is a follow-up question: Let $u\in V(G)$ such that $u$ belongs to some minimum $st$-separator of $G$. Let $S$ be any minimal $st$-separator that does not contain $u$ (i.e., $u\notin S$). Also, let $C_s(S)$ and $C_t(S)$ denote the connected components containing $s$ and $t$ respectively in $G-S$. Is it necessarily the case that $u\in C_s(S)\cup C_t(S)$ ?
– BBK
Apr 6 at 8:41
• Do you know Menger's theorem? If yes, what can be said about the relationship of any minimum separator with any maximum set of disjoint $st$-path? Apr 6 at 11:08
• Yes. The $st$-connectivity of $G$ is the maximum number of internally-disjoint $st$-paths in $G$. I don't see how this implies that for any minimal $st$-separator $S$, every vertex $u\notin S$ that belongs to some minimum $st$-separator necessarily belongs to either $C_s(S)$ or $C_t(S)$.
– BBK
Apr 6 at 13:39
• Use the fact (an easy consequence of Menger's theorem) that for any k disjoint paths $P_1,\ldots,P_k$ and any $st$-separator $S$ of size $k$, $P_i \cap S$ = 1 for each $i$ (each path $P_i$ contains exactly one vertex of $S$). Apr 7 at 5:19
• If $S$ is a minimum $st$-sep then this is indeed the case, because every path meets exactly one vertex from $S$. But a minimal separator can be larger than $k$, and hence cut such a path in more than one position, sending some vertices to connected components other than $C_s(S)$ or $C_t(S)$. Can it be shown that for vertices that belong to a minimum $st$-sep this cannot happen ?
– BBK
Apr 7 at 7:11