An edge is a bridge iff it lies on no cycle
ProvedFamousTheorems.bridge_iff_no_cycle_7aAn edge is a bridge iff it lies on no cycle. Let be an edge of a simple graph . Then is a bridge, meaning that removing it disconnects its endpoints, if and only if no cycle of contains .
This characterisation is used for the structure of graphs through their -edge-connected components, for Robbins' theorem that a graph has a strongly connected orientation if and only if it is connected and bridgeless, and for linear-time bridge-finding algorithms.
Formalization note. Mathlib's SimpleGraph.isBridge_iff_forall_cycle_notMem. G.IsBridge e says that is an edge and its endpoints are not reachable from each other in with deleted. Cycles are closed walks p : G.Walk u u with p.IsCycle, and p.edges is the list of their edges.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem bridge_iff_no_cycle_7a {V : Type*} {G : SimpleGraph V} {e : Sym2 V} (he : e ∈ G.edgeSet) :
G.IsBridge e ↔ ∀ ⦃u : V⦄ (p : G.Walk u u), p.IsCycle → e ∉ p.edges := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.isBridge_iff_forall_cycle_notMem`. Proof here reduces to that Mathlib result.