<p>It does not hold, as can be seen from the red separator in this example.</p>
<p><a href="https://i.sstatic.net/ZtNew.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZtNew.png" alt="couterexample" /></a></p>
<p>Furthermore, a vertex in a minimum separator can be separated from <span class="math-container">$s$</span> and <span class="math-container">$t$</span> by a minimal separator:</p>
<p><a href="https://i.sstatic.net/pCbf2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pCbf2.png" alt="second couterexample" /></a></p>

CC BY-SA 4.0
2022-04-06T08:41:26.237Z
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
CC BY-SA 4.0
2022-04-06T11:08:55.380Z
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?
Guyslain
CC BY-SA 4.0
2022-04-06T13:39:34.093Z
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
CC BY-SA 4.0
2022-04-07T05:19:41.797Z
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$).
Guyslain
CC BY-SA 4.0
2022-04-07T07:11:09.797Z
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
CC BY-SA 4.0
2022-04-07T08:42:11.233Z
Sorry, I misread your comment and thought that $S$ was minimum. I edit the answer with a counter-example to that.
Guyslain
CC BY-SA 4.0
2022-04-06T05:52:52.553Z
2022-04-07T08:43:41.913Z
2022-04-07T08:43:41.913Z
Guyslain
<p>Let <span class="math-container">$G$</span> be an undirected, connected graph, and <span class="math-container">$s,t$</span> non-adjacent vertices in <span class="math-container">$G$</span>.
Denote by <span class="math-container">$k_{st}(G)$</span> the <span class="math-container">$st$</span>-connectivity of <span class="math-container">$G$</span>. That is, <span class="math-container">$k_{st}(G)$</span> is the size of any minimum <span class="math-container">$st$</span>-separator of <span class="math-container">$G$</span>.</p>
<p>(*) It can be shown that if a vertex <span class="math-container">$v$</span> belongs to any minimum <span class="math-container">$st$</span>-separator of <span class="math-container">$G$</span>, then <span class="math-container">$k_{st}(G-v)=k_{st}(G)-1$</span>.</p>
<p>How do you prove the following:
Let <span class="math-container">$S$</span> be a minimal <span class="math-container">$st$</span>-separator of <span class="math-container">$G$</span> that is <strong>not</strong> a minimum <span class="math-container">$st$</span>-separator of <span class="math-container">$G$</span>. Prove that <span class="math-container">$S$</span> contains at least one vertex <span class="math-container">$v\in S$</span> such that <span class="math-container">$k_{st}(G-v)=k_{st}(G)$</span>.</p>
<p>It seems very intuitive that this would hold, especially since (*) can be shown. However, I have yet to find a formal proof...</p>

<graph-theory><graph-algorithms>
Proving a property of minimal st-separators that are not minimum st-separators
BBK
# Proving a property of minimal st-separators that are not minimum st-separators

(Asked by: username_0 on 2022-04-04)

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

**Tags:** graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2022-04-06. Score: 5 | Accepted answer

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

[![couterexample](https://i.sstatic.net/ZtNew.png)](https://i.sstatic.net/ZtNew.png)

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

[![second couterexample](https://i.sstatic.net/pCbf2.png)](https://i.sstatic.net/pCbf2.png)

> **Comments:**
> **username_0**: 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)$ ?  
> **username_1**: 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?  
> **username_0**: 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)$.  
> **username_1**: 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$).  
> **username_0**: 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 ?  
> **username_1**: Sorry, I misread your comment and thought that $S$ was minimum. I edit the answer with a counter-example to that.  

---

