# Minimal cutting sets in connected graphs

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

• 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. – Aaron Meyerowitz Jun 14 '18 at 20:57
• @AaronMeyerowitz What $S_0$ were you thinking about? (See Monroe Eskew's negative answer below) – Dominic van der Zypen Jun 16 '18 at 17:56
• I was wrong. I was thinking of deleting a set of edges. But I might be wrong there too. – Aaron Meyerowitz Jun 16 '18 at 18:28

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\}$.