{"abstract":"Triangle counting includes closed walks through self loops.","category":"Graph algorithm invariants","checks":8,"contract":"Return the number of distinct three-vertex cliques in an undirected graph. Self loops are ignored and parallel declarations count once.","evaluation_group":"model-9282e98be00ac41d","failed_approach":"Counting each adjacent neighbor pair at every vertex without normalization counts every triangle three times.","family":"z-graphs-triangle-distinct-vertices","id":"FA-11736","implementations":{"attempt":{"sha256":"5025c613ee91beea22c88693a30fa31806b4dc5a9de23fdc17990508524d629b","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        adj[u].add(v); adj[v].add(u)\n    return sum(c in adj[b] for a in vertices for b,c in combinations(sorted(adj[a]-{a}),2))\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('loops on adjacent vertices are not triangles', solve([a,b], [(a,a),(a,b),(b,b)]), 0)\ncheck('one triangle', solve([a,b,c], [(a,b),(b,c),(c,a)]), 1)\ncheck('complete four graph', solve([a,b,c,d], list(combinations([a,b,c,d],2))), 4)\ncheck('empty', solve([], []), 0)\ncheck('one loop', solve([a], [(a,a)]), 0)\ncheck('parallel triangle declarations', solve([a,b,c], [(a,b),(a,b),(b,c),(c,a)]), 1)\ncheck('square without diagonals', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), 0)\ncheck('variable-size clique', solve(list(range(N+2)), list(combinations(range(N+2),2))), (N+2)*(N+1)*N//6)\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":"a61b8d8fd58c1dda9bccc7bd356e486782e6ff637c520651b37d4783af0f9b10","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        adj[u].add(v); adj[v].add(u)\n    return sum(c in adj[a] for a in vertices for b in adj[a] for c in adj[b]) // 6\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('loops on adjacent vertices are not triangles', solve([a,b], [(a,a),(a,b),(b,b)]), 0)\ncheck('one triangle', solve([a,b,c], [(a,b),(b,c),(c,a)]), 1)\ncheck('complete four graph', solve([a,b,c,d], list(combinations([a,b,c,d],2))), 4)\ncheck('empty', solve([], []), 0)\ncheck('one loop', solve([a], [(a,a)]), 0)\ncheck('parallel triangle declarations', solve([a,b,c], [(a,b),(a,b),(b,c),(c,a)]), 1)\ncheck('square without diagonals', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), 0)\ncheck('variable-size clique', solve(list(range(N+2)), list(combinations(range(N+2),2))), (N+2)*(N+1)*N//6)\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":"a131c443d6b49443d1351f55021796cee6ce5a437f236e1bbe3bad4c006c3af7","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        adj[u].add(v); adj[v].add(u)\n    return sum(b in adj[a] and c in adj[a] and c in adj[b] for a,b,c in combinations(sorted(vertices),3))\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('loops on adjacent vertices are not triangles', solve([a,b], [(a,a),(a,b),(b,b)]), 0)\ncheck('one triangle', solve([a,b,c], [(a,b),(b,c),(c,a)]), 1)\ncheck('complete four graph', solve([a,b,c,d], list(combinations([a,b,c,d],2))), 4)\ncheck('empty', solve([], []), 0)\ncheck('one loop', solve([a], [(a,a)]), 0)\ncheck('parallel triangle declarations', solve([a,b,c], [(a,b),(a,b),(b,c),(c,a)]), 1)\ncheck('square without diagonals', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), 0)\ncheck('variable-size clique', solve(list(range(N+2)), list(combinations(range(N+2),2))), (N+2)*(N+1)*N//6)\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-triangle-distinct-vertices","generated_at":"2026-09-29T14:38:50.518166+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":"Enumerate unordered triples of distinct vertices and test their three undirected adjacencies.","root_cause":"Length-three closed walks are counted as triangles without requiring three distinct vertices.","sha256":"2cead488fe5fad11bdc78492173a7ffb87dedf5deff879d1506871c78c2a0f32","title":"Triangle counting includes closed walks through self loops · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":38.939,"exit_code":1,"observations":[{"actual":0,"check":"loops on adjacent vertices are not triangles","expected":0,"passed":true},{"actual":3,"check":"one triangle","expected":1,"passed":false},{"actual":12,"check":"complete four graph","expected":4,"passed":false},{"actual":0,"check":"empty","expected":0,"passed":true},{"actual":0,"check":"one loop","expected":0,"passed":true},{"actual":3,"check":"parallel triangle declarations","expected":1,"passed":false},{"actual":0,"check":"square without diagonals","expected":0,"passed":true},{"actual":3,"check":"variable-size clique","expected":1,"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"loops on adjacent vertices are not triangles\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"one triangle\", \"actual\": 3, \"expected\": 1, \"passed\": false}, {\"check\": \"complete four graph\", \"actual\": 12, \"expected\": 4, \"passed\": false}, {\"check\": \"empty\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"one loop\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"parallel triangle declarations\", \"actual\": 3, \"expected\": 1, \"passed\": false}, {\"check\": \"square without diagonals\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"variable-size clique\", \"actual\": 3, \"expected\": 1, \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.647,"exit_code":1,"observations":[{"actual":1,"check":"loops on adjacent vertices are not triangles","expected":0,"passed":false},{"actual":1,"check":"one triangle","expected":1,"passed":true},{"actual":4,"check":"complete four graph","expected":4,"passed":true},{"actual":0,"check":"empty","expected":0,"passed":true},{"actual":0,"check":"one loop","expected":0,"passed":true},{"actual":1,"check":"parallel triangle declarations","expected":1,"passed":true},{"actual":0,"check":"square without diagonals","expected":0,"passed":true},{"actual":1,"check":"variable-size clique","expected":1,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"loops on adjacent vertices are not triangles\", \"actual\": 1, \"expected\": 0, \"passed\": false}, {\"check\": \"one triangle\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"complete four graph\", \"actual\": 4, \"expected\": 4, \"passed\": true}, {\"check\": \"empty\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"one loop\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"parallel triangle declarations\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"square without diagonals\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"variable-size clique\", \"actual\": 1, \"expected\": 1, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.192,"exit_code":0,"observations":[{"actual":0,"check":"loops on adjacent vertices are not triangles","expected":0,"passed":true},{"actual":1,"check":"one triangle","expected":1,"passed":true},{"actual":4,"check":"complete four graph","expected":4,"passed":true},{"actual":0,"check":"empty","expected":0,"passed":true},{"actual":0,"check":"one loop","expected":0,"passed":true},{"actual":1,"check":"parallel triangle declarations","expected":1,"passed":true},{"actual":0,"check":"square without diagonals","expected":0,"passed":true},{"actual":1,"check":"variable-size clique","expected":1,"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"loops on adjacent vertices are not triangles\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"one triangle\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"complete four graph\", \"actual\": 4, \"expected\": 4, \"passed\": true}, {\"check\": \"empty\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"one loop\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"parallel triangle declarations\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"square without diagonals\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"variable-size clique\", \"actual\": 1, \"expected\": 1, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}