# Minimal bridging sets in infinite connected graphs

Let $$G=(V, E)$$ be a connected, simple, undirected graph. We say that $$B\subseteq V$$ is a bridging set if $$B\neq V$$ and removing $$B$$ makes the graph disconnected, or more formally: $$G \setminus B := (V\setminus B\;, \; \{e\in E: e\cap B = \varnothing\})$$ is not connected any more.

Is there an infinite connected graph $$G=(V,E)$$ such that for every bridging set $$B\subseteq V$$ there is a bridging set $$B_1$$ with $$B_1\subseteq B$$ and $$B_1\neq B$$?

• formally an infinite complete graph satisfies the required property (it does not have bridging sets), but this is probably not what you mean? Feb 25, 2021 at 14:26
• It seems like the answer should surely be no by Zorn's lemma, but a proof that chains are bounded below didn't immediately come to me. Feb 25, 2021 at 14:33
• @FedorPetrov Perhaps the definition should be conceptually simplified by removing the unwarranted condition $B\ne V$. Then every graph does have at least one bridging set, namely $V$ (keeping in mind that the empty graph is not connected, as its number of components is $0$ rather than $1$). Feb 25, 2021 at 16:06

Take for $$V = S \coprod T$$ with bijections $$s : \mathbb N \to S$$ and $$t : \mathbb N \to T$$ ; and have the edge set $$K_T \cup \{(s(i),t(j)) \quad\mathtt{ iff }\quad i \le j\}$$.
First, see that $$\forall n$$, $$t(\mathbb N + n)$$ is a bridging set. Indeed, $$s(k)$$ for $$k \ge n$$ is isolated. This gives an infinite strict chain of bridging sets, whose limit is empty (so not a bridging set).
Let $$B$$ be a bridging set. Let's prove that $$B \supset t(\mathbb N + k)$$ for a $$k$$. Suppose it's not the case, that is : $$\forall k \in \mathbb N, \exists N(k), t(N(k)) \notin B$$. Then take two nodes $$u,v$$, those nodes are in $$T \cup s(\mathbb N + n)$$, so both have $$t(N(n))$$ as a neighbourg.
• @PaulMcKenney The Half graph does not have the clique on $T$, though. Feb 25, 2021 at 16:41