{"abstract":"Bipartite validation ignores an unvisited odd-cycle component.","category":"Graph algorithm invariants","checks":8,"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.","evaluation_group":"model-4b9d5bf347f38f7e","failed_approach":"Restarting traversals while dropping self loops wrongly accepts an odd cycle of length one.","family":"z-graphs-bipartite-all-components","id":"FA-11701","implementations":{"attempt":{"sha256":"e95edc36798066cccfde4fc443ea813aad389abd705a25ccb151502803ed7e45","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        if u == v: continue\n        adj[u].add(v); adj[v].add(u)\n    color = {}\n    for root in vertices:\n        if root in color: continue\n        color[root] = 0; todo = [root]\n        while todo:\n            v = todo.pop()\n            for w in adj[v]:\n                if w in color:\n                    if color[w] == color[v]: return False\n                else:\n                    color[w] = 1-color[v]; todo.append(w)\n    return True\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [10*N+i for i in range(4)]\ncheck('isolated first vertex before odd cycle', solve([a,b,c,d], [(b,c),(c,d),(d,b)]), False)\ncheck('isolated first vertex before loop', solve([a,b], [(b,b)]), False)\ncheck('single loop', solve([a], [(a,a)]), False)\ncheck('empty', solve([], []), True)\ncheck('even cycle', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), True)\ncheck('parallel edges', solve([a,b], [(a,b),(a,b)]), True)\ncheck('disconnected edges', solve([a,b,c,d], [(a,b),(c,d)]), True)\ncheck('variable cycle parity', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), (N+2)%2 == 0)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"d01b9bf7c2534c0ebee0aecf6004aca4246b31c9a3e609feb1755fcdda5a5a4c","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        pass\n        adj[u].add(v); adj[v].add(u)\n    color = {}\n    for root in vertices[:1]:\n        if root in color: continue\n        color[root] = 0; todo = [root]\n        while todo:\n            v = todo.pop()\n            for w in adj[v]:\n                if w in color:\n                    if color[w] == color[v]: return False\n                else:\n                    color[w] = 1-color[v]; todo.append(w)\n    return True\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [10*N+i for i in range(4)]\ncheck('isolated first vertex before odd cycle', solve([a,b,c,d], [(b,c),(c,d),(d,b)]), False)\ncheck('isolated first vertex before loop', solve([a,b], [(b,b)]), False)\ncheck('single loop', solve([a], [(a,a)]), False)\ncheck('empty', solve([], []), True)\ncheck('even cycle', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), True)\ncheck('parallel edges', solve([a,b], [(a,b),(a,b)]), True)\ncheck('disconnected edges', solve([a,b,c,d], [(a,b),(c,d)]), True)\ncheck('variable cycle parity', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), (N+2)%2 == 0)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"45837bf067be504a2401d14367b790503a5eac747d518eae048a8c8530ff08e1","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        pass\n        adj[u].add(v); adj[v].add(u)\n    color = {}\n    for root in vertices:\n        if root in color: continue\n        color[root] = 0; todo = [root]\n        while todo:\n            v = todo.pop()\n            for w in adj[v]:\n                if w in color:\n                    if color[w] == color[v]: return False\n                else:\n                    color[w] = 1-color[v]; todo.append(w)\n    return True\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [10*N+i for i in range(4)]\ncheck('isolated first vertex before odd cycle', solve([a,b,c,d], [(b,c),(c,d),(d,b)]), False)\ncheck('isolated first vertex before loop', solve([a,b], [(b,b)]), False)\ncheck('single loop', solve([a], [(a,a)]), False)\ncheck('empty', solve([], []), True)\ncheck('even cycle', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), True)\ncheck('parallel edges', solve([a,b], [(a,b),(a,b)]), True)\ncheck('disconnected edges', solve([a,b,c,d], [(a,b),(c,d)]), True)\ncheck('variable cycle parity', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)]), (N+2)%2 == 0)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"z-graphs-bipartite-all-components","generated_at":"2026-09-29T14:38:50.274803+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"A deterministic in-memory graph model isolates this invariant; no large-graph performance or production graph engine behavior is claimed.","repair":"Start a coloring traversal from every uncolored vertex, and test every edge including self loops.","root_cause":"Two-coloring starts only at the first supplied vertex and never restarts in disconnected components.","sha256":"954f807441d7bac5cb65839a33f3d9c3b3b7533e032f8a19aa23873ed49ef71b","title":"Bipartite validation ignores an unvisited odd-cycle component · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":37.931,"exit_code":1,"observations":[{"actual":false,"check":"isolated first vertex before odd cycle","expected":false,"passed":true},{"actual":true,"check":"isolated first vertex before loop","expected":false,"passed":false},{"actual":true,"check":"single loop","expected":false,"passed":false},{"actual":true,"check":"empty","expected":true,"passed":true},{"actual":true,"check":"even cycle","expected":true,"passed":true},{"actual":true,"check":"parallel edges","expected":true,"passed":true},{"actual":true,"check":"disconnected edges","expected":true,"passed":true},{"actual":false,"check":"variable cycle parity","expected":false,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"isolated first vertex before odd cycle\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"isolated first vertex before loop\", \"actual\": true, \"expected\": false, \"passed\": false}, {\"check\": \"single loop\", \"actual\": true, \"expected\": false, \"passed\": false}, {\"check\": \"empty\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"even cycle\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"parallel edges\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"disconnected edges\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"variable cycle parity\", \"actual\": false, \"expected\": false, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.303,"exit_code":1,"observations":[{"actual":true,"check":"isolated first vertex before odd cycle","expected":false,"passed":false},{"actual":true,"check":"isolated first vertex before loop","expected":false,"passed":false},{"actual":false,"check":"single loop","expected":false,"passed":true},{"actual":true,"check":"empty","expected":true,"passed":true},{"actual":true,"check":"even cycle","expected":true,"passed":true},{"actual":true,"check":"parallel edges","expected":true,"passed":true},{"actual":true,"check":"disconnected edges","expected":true,"passed":true},{"actual":false,"check":"variable cycle parity","expected":false,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"isolated first vertex before odd cycle\", \"actual\": true, \"expected\": false, \"passed\": false}, {\"check\": \"isolated first vertex before loop\", \"actual\": true, \"expected\": false, \"passed\": false}, {\"check\": \"single loop\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"empty\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"even cycle\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"parallel edges\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"disconnected edges\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"variable cycle parity\", \"actual\": false, \"expected\": false, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":37.134,"exit_code":0,"observations":[{"actual":false,"check":"isolated first vertex before odd cycle","expected":false,"passed":true},{"actual":false,"check":"isolated first vertex before loop","expected":false,"passed":true},{"actual":false,"check":"single loop","expected":false,"passed":true},{"actual":true,"check":"empty","expected":true,"passed":true},{"actual":true,"check":"even cycle","expected":true,"passed":true},{"actual":true,"check":"parallel edges","expected":true,"passed":true},{"actual":true,"check":"disconnected edges","expected":true,"passed":true},{"actual":false,"check":"variable cycle parity","expected":false,"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"isolated first vertex before odd cycle\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"isolated first vertex before loop\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"single loop\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"empty\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"even cycle\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"parallel edges\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"disconnected edges\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"variable cycle parity\", \"actual\": false, \"expected\": false, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}