Skip to main content
Became Hot Network Question
Added top-level tag
Link
gmvh
  • 3.1k
  • 6
  • 27
  • 45
Source Link

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