FA-11696 / Graph algorithm invariants / Open access
Parallel edges are all removed when testing a single bridge · case 01
Parallel edges are all removed when testing a single bridge.
ROOT CAUSE
Endpoint pairs substitute for edge identities, so a single-edge deletion removes every parallel edge.
VERIFIED REPAIR
Remove precisely the indexed edge and compare component counts against the original graph.
Unsuccessful approach: Deduplicating parallel edges before deletion still invents bridges absent from the multigraph.
Case contract
Return input indices of bridges in an undirected multigraph. Self loops and parallel edges are allowed. Removing exactly one bridge increases the number of connected components.
Why this case matters
A deterministic in-memory graph model isolates this invariant; no large-graph performance or production graph engine behavior is claimed.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
def components(es):
adj = {v:set() for v in vertices}
for u,v in es:
adj[u].add(v); adj[v].add(u)
seen, count = set(), 0
for v in vertices:
if v in seen: continue
count += 1; seen.add(v); todo = [v]
while todo:
for w in adj[todo.pop()] - seen:
seen.add(w); todo.append(w)
return count
baseline = components(edges)
answer = []
for i,(u,v) in enumerate(edges):
remaining = [(a,b) for a,b in edges if {a,b} != {u,v}]
if components(remaining) > baseline:
answer.append(i)
return answer
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('parallel pair', solve([a,b], [(a,b),(a,b)]), [])
check('opposite endpoint order', solve([a,b], [(a,b),(b,a)]), [])
check('parallel pair with tail', solve([a,b,c], [(a,b),(a,b),(b,c)]), [2])
check('single edge', solve([a,b], [(a,b)]), [0])
check('self loop', solve([a], [(a,a)]), [])
check('empty', solve([], []), [])
check('disconnected forest', solve([a,b,c], [(a,b)]), [0])
check('variable-length forest', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N)))
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| parallel pair | [0, 1] | [] | Failed |
| opposite endpoint order | [0, 1] | [] | Failed |
| parallel pair with tail | [0, 1, 2] | [2] | Failed |
| single edge | [0] | [0] | Passed |
| self loop | [] | [] | Passed |
| empty | [] | [] | Passed |
| disconnected forest | [0] | [0] | Passed |
| variable-length forest | [0] | [0] | Passed |
SHA-256 / eac0fa6cb18da1bbcb14f76470e5ed219968428d5226733ad299c97fdc22e11e
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
def components(es):
adj = {v:set() for v in vertices}
for u,v in es:
adj[u].add(v); adj[v].add(u)
seen, count = set(), 0
for v in vertices:
if v in seen: continue
count += 1; seen.add(v); todo = [v]
while todo:
for w in adj[todo.pop()] - seen:
seen.add(w); todo.append(w)
return count
baseline = components(edges)
answer = []
for i,(u,v) in enumerate(edges):
remaining = [tuple(p) for p in {tuple(sorted(e)) for j,e in enumerate(edges) if j != i} if set(p) != {u,v}]
if components(remaining) > baseline:
answer.append(i)
return answer
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('parallel pair', solve([a,b], [(a,b),(a,b)]), [])
check('opposite endpoint order', solve([a,b], [(a,b),(b,a)]), [])
check('parallel pair with tail', solve([a,b,c], [(a,b),(a,b),(b,c)]), [2])
check('single edge', solve([a,b], [(a,b)]), [0])
check('self loop', solve([a], [(a,a)]), [])
check('empty', solve([], []), [])
check('disconnected forest', solve([a,b,c], [(a,b)]), [0])
check('variable-length forest', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N)))
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| parallel pair | [0, 1] | [] | Failed |
| opposite endpoint order | [0, 1] | [] | Failed |
| parallel pair with tail | [0, 1, 2] | [2] | Failed |
| single edge | [0] | [0] | Passed |
| self loop | [] | [] | Passed |
| empty | [] | [] | Passed |
| disconnected forest | [0] | [0] | Passed |
| variable-length forest | [0] | [0] | Passed |
SHA-256 / 3d29a29ec723fde99667257bc97bc3eee4085cf98b56dcbaa02511787a25b82e
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
def components(es):
adj = {v:set() for v in vertices}
for u,v in es:
adj[u].add(v); adj[v].add(u)
seen, count = set(), 0
for v in vertices:
if v in seen: continue
count += 1; seen.add(v); todo = [v]
while todo:
for w in adj[todo.pop()] - seen:
seen.add(w); todo.append(w)
return count
baseline = components(edges)
answer = []
for i,(u,v) in enumerate(edges):
remaining = edges[:i] + edges[i+1:]
if components(remaining) > baseline:
answer.append(i)
return answer
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('parallel pair', solve([a,b], [(a,b),(a,b)]), [])
check('opposite endpoint order', solve([a,b], [(a,b),(b,a)]), [])
check('parallel pair with tail', solve([a,b,c], [(a,b),(a,b),(b,c)]), [2])
check('single edge', solve([a,b], [(a,b)]), [0])
check('self loop', solve([a], [(a,a)]), [])
check('empty', solve([], []), [])
check('disconnected forest', solve([a,b,c], [(a,b)]), [0])
check('variable-length forest', solve(list(range(N+1)), [(i,i+1) for i in range(N)]), list(range(N)))
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| parallel pair | [] | [] | Passed |
| opposite endpoint order | [] | [] | Passed |
| parallel pair with tail | [2] | [2] | Passed |
| single edge | [0] | [0] | Passed |
| self loop | [] | [] | Passed |
| empty | [] | [] | Passed |
| disconnected forest | [0] | [0] | Passed |
| variable-length forest | [0] | [0] | Passed |
SHA-256 / 5390da12544d7019cb2f8a58d1cfede952ea651e4e4d1e1b2ecfe1c19bd04285
Verification & scope
Small explicit graphs only; exhaustive reference algorithms emphasize semantics rather than asymptotic performance. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:38:50.233349+00:00.
Case digest / 9e5698ad7a32d8dc216724c270b8a5ca1dd7fb8112646992a77edfe593bd0478