2
$\begingroup$

Let $G=(V,E)$ be a simple, undirected and connected graph. We say that $S\subseteq V$ is a cutting set if $S\neq V$ and the induced subgraph on $V\setminus S$ is not connected any more.

If $S \subseteq V$ is a cutting set of $G$, is there a cutting set $S_0\subseteq S$ of $G$ such that for all $x\in S_0$ the set $S_0\setminus \{x\}$ is no longer a cutting set?

(This question has an easy positive answer for finite graphs, so it is only interesting for infinite graphs.)

Improve this question
$\endgroup$
3
  • $\begingroup$ Yes. The induced graph would have to have exactly two connected components. Pick a component of $V \backslash S$ to be a component of $V \backslash S_0$ and figure out what $S_0$ should be. $\endgroup$ – Aaron Meyerowitz Jun 14 '18 at 20:57
  • $\begingroup$ @AaronMeyerowitz What $S_0$ were you thinking about? (See Monroe Eskew's negative answer below) $\endgroup$ – Dominic van der Zypen Jun 16 '18 at 17:56
  • $\begingroup$ I was wrong. I was thinking of deleting a set of edges. But I might be wrong there too. $\endgroup$ – Aaron Meyerowitz Jun 16 '18 at 18:28
2
$\begingroup$

No. Here is a counterexample.

Let $V = \{ x_n,y_n : n \in \mathbb N \}$. Put $x_n E y_m$ and when $n \leq m$, and put an edge between any two $y_n$'s. If $A \subseteq \mathbb N$ is cofinite, then the induced subgraph on $V \setminus \{ y_n : n \in A \}$ is not connected, since there are no edges with endpoint $x_n$ when $n > \sup(\mathbb N \setminus A)$. But if $\mathbb N \setminus A$ is infinite, then for any $a,b \in V \setminus \{ y_n : n \in A \}$, there is a large enough $m \in \mathbb N \setminus A$ such that $aEy_mEb$. Therefore, there is no minimal cutting set contained in $\{ y_n : n \in \mathbb N\}$.

Improve this answer
$\endgroup$

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.