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



Minimal cutting sets in connected graphs
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\}$.


