FA-11736 / Graph algorithm invariants / Open access
Triangle counting includes closed walks through self loops · case 01
Triangle counting includes closed walks through self loops.
ROOT CAUSE
Length-three closed walks are counted as triangles without requiring three distinct vertices.
VERIFIED REPAIR
Enumerate unordered triples of distinct vertices and test their three undirected adjacencies.
Unsuccessful approach: Counting each adjacent neighbor pair at every vertex without normalization counts every triangle three times.
Case contract
Return the number of distinct three-vertex cliques in an undirected graph. Self loops are ignored and parallel declarations count once.
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:
adj[u].add(v); adj[v].add(u)
return sum(c in adj[a] for a in vertices for b in adj[a] for c in adj[b]) // 6
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('loops on adjacent vertices are not triangles', solve([a,b], [(a,a),(a,b),(b,b)]), 0)
check('one triangle', solve([a,b,c], [(a,b),(b,c),(c,a)]), 1)
check('complete four graph', solve([a,b,c,d], list(combinations([a,b,c,d],2))), 4)
check('empty', solve([], []), 0)
check('one loop', solve([a], [(a,a)]), 0)
check('parallel triangle declarations', solve([a,b,c], [(a,b),(a,b),(b,c),(c,a)]), 1)
check('square without diagonals', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), 0)
check('variable-size clique', solve(list(range(N+2)), list(combinations(range(N+2),2))), (N+2)*(N+1)*N//6)
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 |
|---|---|---|---|
| loops on adjacent vertices are not triangles | 1 | 0 | Failed |
| one triangle | 1 | 1 | Passed |
| complete four graph | 4 | 4 | Passed |
| empty | 0 | 0 | Passed |
| one loop | 0 | 0 | Passed |
| parallel triangle declarations | 1 | 1 | Passed |
| square without diagonals | 0 | 0 | Passed |
| variable-size clique | 1 | 1 | Passed |
SHA-256 / a61b8d8fd58c1dda9bccc7bd356e486782e6ff637c520651b37d4783af0f9b10
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:
adj[u].add(v); adj[v].add(u)
return sum(c in adj[b] for a in vertices for b,c in combinations(sorted(adj[a]-{a}),2))
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('loops on adjacent vertices are not triangles', solve([a,b], [(a,a),(a,b),(b,b)]), 0)
check('one triangle', solve([a,b,c], [(a,b),(b,c),(c,a)]), 1)
check('complete four graph', solve([a,b,c,d], list(combinations([a,b,c,d],2))), 4)
check('empty', solve([], []), 0)
check('one loop', solve([a], [(a,a)]), 0)
check('parallel triangle declarations', solve([a,b,c], [(a,b),(a,b),(b,c),(c,a)]), 1)
check('square without diagonals', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), 0)
check('variable-size clique', solve(list(range(N+2)), list(combinations(range(N+2),2))), (N+2)*(N+1)*N//6)
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 |
|---|---|---|---|
| loops on adjacent vertices are not triangles | 0 | 0 | Passed |
| one triangle | 3 | 1 | Failed |
| complete four graph | 12 | 4 | Failed |
| empty | 0 | 0 | Passed |
| one loop | 0 | 0 | Passed |
| parallel triangle declarations | 3 | 1 | Failed |
| square without diagonals | 0 | 0 | Passed |
| variable-size clique | 3 | 1 | Failed |
SHA-256 / 5025c613ee91beea22c88693a30fa31806b4dc5a9de23fdc17990508524d629b
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:
adj[u].add(v); adj[v].add(u)
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))
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('loops on adjacent vertices are not triangles', solve([a,b], [(a,a),(a,b),(b,b)]), 0)
check('one triangle', solve([a,b,c], [(a,b),(b,c),(c,a)]), 1)
check('complete four graph', solve([a,b,c,d], list(combinations([a,b,c,d],2))), 4)
check('empty', solve([], []), 0)
check('one loop', solve([a], [(a,a)]), 0)
check('parallel triangle declarations', solve([a,b,c], [(a,b),(a,b),(b,c),(c,a)]), 1)
check('square without diagonals', solve([a,b,c,d], [(a,b),(b,c),(c,d),(d,a)]), 0)
check('variable-size clique', solve(list(range(N+2)), list(combinations(range(N+2),2))), (N+2)*(N+1)*N//6)
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 |
|---|---|---|---|
| loops on adjacent vertices are not triangles | 0 | 0 | Passed |
| one triangle | 1 | 1 | Passed |
| complete four graph | 4 | 4 | Passed |
| empty | 0 | 0 | Passed |
| one loop | 0 | 0 | Passed |
| parallel triangle declarations | 1 | 1 | Passed |
| square without diagonals | 0 | 0 | Passed |
| variable-size clique | 1 | 1 | Passed |
SHA-256 / a131c443d6b49443d1351f55021796cee6ce5a437f236e1bbe3bad4c006c3af7
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.518166+00:00.
Case digest / 2cead488fe5fad11bdc78492173a7ffb87dedf5deff879d1506871c78c2a0f32