FA-11701 / Graph algorithm invariants / Open access

Bipartite validation ignores an unvisited odd-cycle component · case 01

Bipartite validation ignores an unvisited odd-cycle component.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Two-coloring starts only at the first supplied vertex and never restarts in disconnected components.

VERIFIED REPAIR

Start a coloring traversal from every uncolored vertex, and test every edge including self loops.

Unsuccessful approach: Restarting traversals while dropping self loops wrongly accepts an odd cycle of length one.

Case contract

Return whether the entire undirected graph is bipartite, including disconnected components. A self loop makes it nonbipartite; duplicate edges do not change the answer.

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):
    adj = {v:set() for v in vertices}
    for u,v in edges:
        pass
        adj[u].add(v); adj[v].add(u)
    color = {}
    for root in vertices[:1]:
        if root in color: continue
        color[root] = 0; todo = [root]
        while todo:
            v = todo.pop()
            for w in adj[v]:
                if w in color:
                    if color[w] == color[v]: return False
                else:
                    color[w] = 1-color[v]; todo.append(w)
    return True
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [10*N+i for i in range(4)]
check('isolated first vertex before odd cycle', solve([a,b,c,d], [(b,c),(c,d),(d,b)]), False)
check('isolated first vertex before loop', solve([a,b], [(b,b)]), False)
check('single loop', solve([a], [(a,a)]), False)
check('empty', solve([], []), True)
check('even cycle', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), True)
check('parallel edges', solve([a,b], [(a,b),(a,b)]), True)
check('disconnected edges', solve([a,b,c,d], [(a,b),(c,d)]), True)
check('variable cycle parity', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), (N+2)%2 == 0)
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
isolated first vertex before odd cycle	`True`	`False`	Failed
isolated first vertex before loop	`True`	`False`	Failed
single loop	`False`	`False`	Passed
empty	`True`	`True`	Passed
even cycle	`True`	`True`	Passed
parallel edges	`True`	`True`	Passed
disconnected edges	`True`	`True`	Passed
variable cycle parity	`False`	`False`	Passed

SHA-256 / d01b9bf7c2534c0ebee0aecf6004aca4246b31c9a3e609feb1755fcdda5a5a4c

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):
    adj = {v:set() for v in vertices}
    for u,v in edges:
        if u == v: continue
        adj[u].add(v); adj[v].add(u)
    color = {}
    for root in vertices:
        if root in color: continue
        color[root] = 0; todo = [root]
        while todo:
            v = todo.pop()
            for w in adj[v]:
                if w in color:
                    if color[w] == color[v]: return False
                else:
                    color[w] = 1-color[v]; todo.append(w)
    return True
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [10*N+i for i in range(4)]
check('isolated first vertex before odd cycle', solve([a,b,c,d], [(b,c),(c,d),(d,b)]), False)
check('isolated first vertex before loop', solve([a,b], [(b,b)]), False)
check('single loop', solve([a], [(a,a)]), False)
check('empty', solve([], []), True)
check('even cycle', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), True)
check('parallel edges', solve([a,b], [(a,b),(a,b)]), True)
check('disconnected edges', solve([a,b,c,d], [(a,b),(c,d)]), True)
check('variable cycle parity', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), (N+2)%2 == 0)
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
isolated first vertex before odd cycle	`False`	`False`	Passed
isolated first vertex before loop	`True`	`False`	Failed
single loop	`True`	`False`	Failed
empty	`True`	`True`	Passed
even cycle	`True`	`True`	Passed
parallel edges	`True`	`True`	Passed
disconnected edges	`True`	`True`	Passed
variable cycle parity	`False`	`False`	Passed

SHA-256 / e95edc36798066cccfde4fc443ea813aad389abd705a25ccb151502803ed7e45

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):
    adj = {v:set() for v in vertices}
    for u,v in edges:
        pass
        adj[u].add(v); adj[v].add(u)
    color = {}
    for root in vertices:
        if root in color: continue
        color[root] = 0; todo = [root]
        while todo:
            v = todo.pop()
            for w in adj[v]:
                if w in color:
                    if color[w] == color[v]: return False
                else:
                    color[w] = 1-color[v]; todo.append(w)
    return True
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [10*N+i for i in range(4)]
check('isolated first vertex before odd cycle', solve([a,b,c,d], [(b,c),(c,d),(d,b)]), False)
check('isolated first vertex before loop', solve([a,b], [(b,b)]), False)
check('single loop', solve([a], [(a,a)]), False)
check('empty', solve([], []), True)
check('even cycle', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), True)
check('parallel edges', solve([a,b], [(a,b),(a,b)]), True)
check('disconnected edges', solve([a,b,c,d], [(a,b),(c,d)]), True)
check('variable cycle parity', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), (N+2)%2 == 0)
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
isolated first vertex before odd cycle	`False`	`False`	Passed
isolated first vertex before loop	`False`	`False`	Passed
single loop	`False`	`False`	Passed
empty	`True`	`True`	Passed
even cycle	`True`	`True`	Passed
parallel edges	`True`	`True`	Passed
disconnected edges	`True`	`True`	Passed
variable cycle parity	`False`	`False`	Passed

SHA-256 / 45837bf067be504a2401d14367b790503a5eac747d518eae048a8c8530ff08e1

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.274803+00:00.

Case digest / 954f807441d7bac5cb65839a33f3d9c3b3b7533e032f8a19aa23873ed49ef71b