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$?

  • 1
    $\begingroup$ formally an infinite complete graph satisfies the required property (it does not have bridging sets), but this is probably not what you mean? $\endgroup$ – Fedor Petrov Feb 25 at 14:26
  • $\begingroup$ 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. $\endgroup$ – lambda Feb 25 at 14:33
  • 1
    $\begingroup$ @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$). $\endgroup$ – Emil Jeřábek Feb 25 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\}$.

Graph awful drawing

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.

  • 1
    $\begingroup$ To construct this, I had to first realize that in any solution, every bridging set must : - Be infinite - Cut the graph in infinite number of connected component This didn't leave much choice, and after trying to prove this was impossible, well... $\endgroup$ – Hugo Manet Feb 25 at 15:39
  • 2
    $\begingroup$ Nice! For reference purposes, this is sometimes called the (infinite) Half Graph: en.wikipedia.org/wiki/Half_graph. $\endgroup$ – Paul McKenney Feb 25 at 16:34
  • $\begingroup$ @PaulMcKenney The Half graph does not have the clique on $T$, though. $\endgroup$ – Emil Jeřábek Feb 25 at 16:41
  • $\begingroup$ Fantastic construction, thanks Hugo! $\endgroup$ – Dominic van der Zypen Feb 25 at 19:15

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.