Non-Blocker

graph-theory

Definition

Non-Blocker

Let be a connected graph. A subset of edges is a non-blocker of if the subgraph is still connected.

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

Connection to Spanning Trees

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