{"abstract":"Euler trail feasibility checks parity without edge connectivity.","category":"Graph algorithm invariants","checks":8,"contract":"Return whether an undirected multigraph has a trail using every edge exactly once. Zero edges are feasible; isolated vertices do not constrain the trail. Self loops contribute degree two.","contract_signature":"vertices, edges","evaluation_group":"model-64bd05ee9e7a221e","failed_approach":"Requiring all declared vertices to be connected incorrectly rejects harmless isolated vertices.","family":"z-graphs-euler-active-connectivity","id":"FA-11711","implementations":{"attempt":{"sha256":"04f4c9d60514bf2bc7242a5e985f7ee00cf109611efd626ce0aa2af9b8d1c3d0","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    degree = {v:0 for v in vertices}\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        degree[u] += 1; degree[v] += 1\n        adj[u].add(v); adj[v].add(u)\n    if sum(d % 2 for d in degree.values()) not in (0,2): return False\n    active = set(vertices)\n    if not active: return True\n    seen, todo = {min(active)}, [min(active)]\n    while todo:\n        for w in adj[todo.pop()] - seen:\n            seen.add(w); todo.append(w)\n    return active <= seen\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [N*10+i for i in range(4)]\ncheck('two disconnected loops', solve([a,b], [(a,a),(b,b)]), False)\ncheck('isolated vertex allowed', solve([a,b,c], [(a,b)]), True)\ncheck('empty declared graph', solve([a,b], []), True)\ncheck('no vertices', solve([], []), True)\ncheck('four odd degrees', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), False)\ncheck('parallel circuit', solve([a,b], [(a,b),(b,a)]), True)\ncheck('loop and trail', solve([a,b], [(a,a),(a,b)]), True)\ncheck('variable number of loop components', solve(list(range(N)), [(i,i) for i in range(N)]), N == 1)\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":"e7b553d69ca088d8de3dcc49cf26fbf6a963fa53dfe7a48d89220a618629278f","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    degree = {v:0 for v in vertices}\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        degree[u] += 1; degree[v] += 1\n        adj[u].add(v); adj[v].add(u)\n    if sum(d % 2 for d in degree.values()) not in (0,2): return False\n    active = set()\n    if not active: return True\n    seen, todo = {min(active)}, [min(active)]\n    while todo:\n        for w in adj[todo.pop()] - seen:\n            seen.add(w); 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 = [N*10+i for i in range(4)]\ncheck('two disconnected loops', solve([a,b], [(a,a),(b,b)]), False)\ncheck('isolated vertex allowed', solve([a,b,c], [(a,b)]), True)\ncheck('empty declared graph', solve([a,b], []), True)\ncheck('no vertices', solve([], []), True)\ncheck('four odd degrees', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), False)\ncheck('parallel circuit', solve([a,b], [(a,b),(b,a)]), True)\ncheck('loop and trail', solve([a,b], [(a,a),(a,b)]), True)\ncheck('variable number of loop components', solve(list(range(N)), [(i,i) for i in range(N)]), N == 1)\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-euler-active-connectivity","generated_at":"2026-09-29T14:38:50.350560+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.","root_cause":"Even degree or two odd degrees is treated as sufficient without requiring a connected edge-bearing component.","sha256":"19b35249c322832532581fb7bb10da60a06901ba10518467275abe865bec6b1b","title":"Euler trail feasibility checks parity without edge connectivity · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":38.399,"exit_code":1,"observations":[{"actual":false,"check":"two disconnected loops","expected":false,"passed":true},{"actual":false,"check":"isolated vertex allowed","expected":true,"passed":false},{"actual":false,"check":"empty declared graph","expected":true,"passed":false},{"actual":true,"check":"no vertices","expected":true,"passed":true},{"actual":false,"check":"four odd degrees","expected":false,"passed":true},{"actual":true,"check":"parallel circuit","expected":true,"passed":true},{"actual":true,"check":"loop and trail","expected":true,"passed":true},{"actual":true,"check":"variable number of loop components","expected":true,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two disconnected loops\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"isolated vertex allowed\", \"actual\": false, \"expected\": true, \"passed\": false}, {\"check\": \"empty declared graph\", \"actual\": false, \"expected\": true, \"passed\": false}, {\"check\": \"no vertices\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"four odd degrees\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"parallel circuit\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"loop and trail\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"variable number of loop components\", \"actual\": true, \"expected\": true, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":38.555,"exit_code":1,"observations":[{"actual":true,"check":"two disconnected loops","expected":false,"passed":false},{"actual":true,"check":"isolated vertex allowed","expected":true,"passed":true},{"actual":true,"check":"empty declared graph","expected":true,"passed":true},{"actual":true,"check":"no vertices","expected":true,"passed":true},{"actual":false,"check":"four odd degrees","expected":false,"passed":true},{"actual":true,"check":"parallel circuit","expected":true,"passed":true},{"actual":true,"check":"loop and trail","expected":true,"passed":true},{"actual":true,"check":"variable number of loop components","expected":true,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two disconnected loops\", \"actual\": true, \"expected\": false, \"passed\": false}, {\"check\": \"isolated vertex allowed\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"empty declared graph\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"no vertices\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"four odd degrees\", \"actual\": false, \"expected\": false, \"passed\": true}, {\"check\": \"parallel circuit\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"loop and trail\", \"actual\": true, \"expected\": true, \"passed\": true}, {\"check\": \"variable number of loop components\", \"actual\": true, \"expected\": true, \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}