5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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
    Commented Feb 25, 2021 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
    Commented Feb 25, 2021 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
    Commented Feb 25, 2021 at 16:06

1 Answer 1

Reset to default
6
$\begingroup$

Yes.

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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Feb 25, 2021 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
    Commented Feb 25, 2021 at 16:34
  • $\begingroup$ @PaulMcKenney The Half graph does not have the clique on $T$, though. $\endgroup$
    – Emil Jeřábek
    Commented Feb 25, 2021 at 16:41
  • $\begingroup$ Fantastic construction, thanks Hugo! $\endgroup$
    – Dominic van der Zypen
    Commented Feb 25, 2021 at 19:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .