Non-Blocker

graph-theory

Definition

Non-Blocker

Let $G=(V,E)$ be a connected graph. A subset of edges $N\subseteq E$ is a non-blocker of $G$ if the subgraph $G-N=(V,E\setminus N)$ is still connected.

The dashed edges form a non-blocker $N$ consisting of the edges $b$–$c$ and $a$–$c$. Removing them leaves $G-N$ connected, because the remaining edges contain a spanning tree of $G$.

Connection to Spanning Trees

A non-blocker is a set of edges that $G$ can spare for connectivity. The criterion is exactly that $E\setminus N$ still contains a spanning tree of $G$, since a graph is connected iff it contains one. Equivalently, $N$ is a non-blocker iff $N\subseteq E\setminus T$ for some spanning tree $T$. The maximal non-blockers are precisely $E\setminus T$, so the redundant edges of $G$ are exactly those that lie outside some spanning tree.