{"abstract":"Core decomposition stops after deleting only the initial low-degree frontier.","category":"Graph algorithm invariants","checks":8,"contract":"Return sorted vertices of the k-core of a simple undirected loopless graph, for nonnegative integer k. Repeated edges are ignored; all vertices survive k=0.","contract_signature":"vertices, edges, k","evaluation_group":"model-a7a197fe36592e13","failed_approach":"Subtracting only one from each original degree guesses the cascade rather than measuring surviving neighbors.","family":"z-graphs-core-cascading-peel","id":"FA-11726","implementations":{"attempt":{"sha256":"22c7f09f8b312f3d5e8ad35309c25f58c5acebeac1c0b4f40a797393f420cbc2","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges, k):\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        adj[u].add(v); adj[v].add(u)\n    active = set(vertices)\n    while True:\n        removed = {v for v in active if len(adj[v]) - (bool(adj[v] - active)) < k}\n        if not removed: break\n        active -= removed\n        pass\n    return sorted(active)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d,e = [10*N+i for i in range(5)]\ncheck('path cascade', solve([a,b,c,d,e], [(a,b),(b,c),(c,d),(d,e)], 2), [])\ncheck('star center loses multiple neighbors', solve([a,b,c,d], [(a,b),(a,c),(a,d)], 2), [])\ncheck('triangle survives', solve([a,b,c,d], [(a,b),(b,c),(c,a),(c,d)], 2), [a,b,c])\ncheck('zero threshold', solve([a,b], [], 0), [a,b])\ncheck('isolates fail positive threshold', solve([a,b], [], 1), [])\ncheck('empty', solve([], [], N), [])\ncheck('duplicate edges not degree inflation', solve([a,b], [(a,b),(a,b)], 2), [])\ncheck('variable-size cycle core', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)], 2), list(range(N+2)))\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":"206abf336d5130d07916a1bd07b3545982b35047b9fd7577ce58aaa3632b2f38","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges, k):\n    adj = {v:set() for v in vertices}\n    for u,v in edges:\n        adj[u].add(v); adj[v].add(u)\n    active = set(vertices)\n    while True:\n        removed = {v for v in active if len(adj[v] & active) < k}\n        if not removed: break\n        active -= removed\n        break\n    return sorted(active)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d,e = [10*N+i for i in range(5)]\ncheck('path cascade', solve([a,b,c,d,e], [(a,b),(b,c),(c,d),(d,e)], 2), [])\ncheck('star center loses multiple neighbors', solve([a,b,c,d], [(a,b),(a,c),(a,d)], 2), [])\ncheck('triangle survives', solve([a,b,c,d], [(a,b),(b,c),(c,a),(c,d)], 2), [a,b,c])\ncheck('zero threshold', solve([a,b], [], 0), [a,b])\ncheck('isolates fail positive threshold', solve([a,b], [], 1), [])\ncheck('empty', solve([], [], N), [])\ncheck('duplicate edges not degree inflation', solve([a,b], [(a,b),(a,b)], 2), [])\ncheck('variable-size cycle core', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)], 2), list(range(N+2)))\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-core-cascading-peel","generated_at":"2026-09-29T14:38:50.480684+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":"Degrees are not recomputed after vertices disappear, preventing cascading removals.","sha256":"67fcc09d81cffbeb473eb2d8f2b6ea8fb764ade56f171a9859e38440af5f9476","title":"Core decomposition stops after deleting only the initial low-degree frontier · 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":40.591,"exit_code":1,"observations":[{"actual":[],"check":"path cascade","expected":[],"passed":true},{"actual":[10],"check":"star center loses multiple neighbors","expected":[],"passed":false},{"actual":[10,11,12],"check":"triangle survives","expected":[10,11,12],"passed":true},{"actual":[10,11],"check":"zero threshold","expected":[10,11],"passed":true},{"actual":[],"check":"isolates fail positive threshold","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[],"check":"duplicate edges not degree inflation","expected":[],"passed":true},{"actual":[0,1,2],"check":"variable-size cycle core","expected":[0,1,2],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"path cascade\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"star center loses multiple neighbors\", \"actual\": [10], \"expected\": [], \"passed\": false}, {\"check\": \"triangle survives\", \"actual\": [10, 11, 12], \"expected\": [10, 11, 12], \"passed\": true}, {\"check\": \"zero threshold\", \"actual\": [10, 11], \"expected\": [10, 11], \"passed\": true}, {\"check\": \"isolates fail positive threshold\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"duplicate edges not degree inflation\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"variable-size cycle core\", \"actual\": [0, 1, 2], \"expected\": [0, 1, 2], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.652,"exit_code":1,"observations":[{"actual":[11,12,13],"check":"path cascade","expected":[],"passed":false},{"actual":[10],"check":"star center loses multiple neighbors","expected":[],"passed":false},{"actual":[10,11,12],"check":"triangle survives","expected":[10,11,12],"passed":true},{"actual":[10,11],"check":"zero threshold","expected":[10,11],"passed":true},{"actual":[],"check":"isolates fail positive threshold","expected":[],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[],"check":"duplicate edges not degree inflation","expected":[],"passed":true},{"actual":[0,1,2],"check":"variable-size cycle core","expected":[0,1,2],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"path cascade\", \"actual\": [11, 12, 13], \"expected\": [], \"passed\": false}, {\"check\": \"star center loses multiple neighbors\", \"actual\": [10], \"expected\": [], \"passed\": false}, {\"check\": \"triangle survives\", \"actual\": [10, 11, 12], \"expected\": [10, 11, 12], \"passed\": true}, {\"check\": \"zero threshold\", \"actual\": [10, 11], \"expected\": [10, 11], \"passed\": true}, {\"check\": \"isolates fail positive threshold\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"duplicate edges not degree inflation\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"variable-size cycle core\", \"actual\": [0, 1, 2], \"expected\": [0, 1, 2], \"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."}}