FA-11711 / Graph algorithm invariants / Open access

Euler trail feasibility checks parity without edge connectivity · case 01

Euler trail feasibility checks parity without edge connectivity.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Even degree or two odd degrees is treated as sufficient without requiring a connected edge-bearing component.

THE FAILURE

Even degree or two odd degrees is treated as sufficient without requiring a connected edge-bearing component.

Unsuccessful approach: Requiring all declared vertices to be connected incorrectly rejects harmless isolated vertices.

Case 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.

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):
    degree = {v:0 for v in vertices}
    adj = {v:set() for v in vertices}
    for u,v in edges:
        degree[u] += 1; degree[v] += 1
        adj[u].add(v); adj[v].add(u)
    if sum(d % 2 for d in degree.values()) not in (0,2): return False
    active = set()
    if not active: return True
    seen, todo = {min(active)}, [min(active)]
    while todo:
        for w in adj[todo.pop()] - seen:
            seen.add(w); todo.append(w)
    return True
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [N*10+i for i in range(4)]
check('two disconnected loops', solve([a,b], [(a,a),(b,b)]), False)
check('isolated vertex allowed', solve([a,b,c], [(a,b)]), True)
check('empty declared graph', solve([a,b], []), True)
check('no vertices', solve([], []), True)
check('four odd degrees', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), False)
check('parallel circuit', solve([a,b], [(a,b),(b,a)]), True)
check('loop and trail', solve([a,b], [(a,a),(a,b)]), True)
check('variable number of loop components', solve(list(range(N)), [(i,i) for i in range(N)]), N == 1)
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
two disconnected loops	`True`	`False`	Failed
isolated vertex allowed	`True`	`True`	Passed
empty declared graph	`True`	`True`	Passed
no vertices	`True`	`True`	Passed
four odd degrees	`False`	`False`	Passed
parallel circuit	`True`	`True`	Passed
loop and trail	`True`	`True`	Passed
variable number of loop components	`True`	`True`	Passed

SHA-256 / e7b553d69ca088d8de3dcc49cf26fbf6a963fa53dfe7a48d89220a618629278f

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):
    degree = {v:0 for v in vertices}
    adj = {v:set() for v in vertices}
    for u,v in edges:
        degree[u] += 1; degree[v] += 1
        adj[u].add(v); adj[v].add(u)
    if sum(d % 2 for d in degree.values()) not in (0,2): return False
    active = set(vertices)
    if not active: return True
    seen, todo = {min(active)}, [min(active)]
    while todo:
        for w in adj[todo.pop()] - seen:
            seen.add(w); todo.append(w)
    return active <= seen
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [N*10+i for i in range(4)]
check('two disconnected loops', solve([a,b], [(a,a),(b,b)]), False)
check('isolated vertex allowed', solve([a,b,c], [(a,b)]), True)
check('empty declared graph', solve([a,b], []), True)
check('no vertices', solve([], []), True)
check('four odd degrees', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), False)
check('parallel circuit', solve([a,b], [(a,b),(b,a)]), True)
check('loop and trail', solve([a,b], [(a,a),(a,b)]), True)
check('variable number of loop components', solve(list(range(N)), [(i,i) for i in range(N)]), N == 1)
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
two disconnected loops	`False`	`False`	Passed
isolated vertex allowed	`False`	`True`	Failed
empty declared graph	`False`	`True`	Failed
no vertices	`True`	`True`	Passed
four odd degrees	`False`	`False`	Passed
parallel circuit	`True`	`True`	Passed
loop and trail	`True`	`True`	Passed
variable number of loop components	`True`	`True`	Passed

SHA-256 / 04f4c9d60514bf2bc7242a5e985f7ee00cf109611efd626ce0aa2af9b8d1c3d0

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

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.350560+00:00.

Case digest / 19b35249c322832532581fb7bb10da60a06901ba10518467275abe865bec6b1b