2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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

couterexample

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

second couterexample

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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)$ ? $\endgroup$
    – BBK
    Apr 6 at 8:41
  • $\begingroup$ 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? $\endgroup$
    – Guyslain
    Apr 6 at 11:08
  • $\begingroup$ 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)$. $\endgroup$
    – BBK
    Apr 6 at 13:39
  • $\begingroup$ 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$). $\endgroup$
    – Guyslain
    Apr 7 at 5:19
  • $\begingroup$ 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 ? $\endgroup$
    – BBK
    Apr 7 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.