#!/usr/bin/env python3 """ ega-verify.py — verification companion to Edge-Attachment Profiles of Graphs: An Exact Characterization Brian Klemm, August 2026 https://brianklemm.com/publications/EdgeAttachmentProfiles.pdf Every result in the paper is proved; this script is corroboration, not evidence. It reproduces each bullet of Appendix A and prints PASS/FAIL for each. No dependencies. Python 3.8+. python3 ega-verify.py # standard run, ~10 seconds python3 ega-verify.py --full # adds exhaustive graph enumeration at n=7, ~3 minutes python3 ega-verify.py --terms # just print the sequence (the OEIS b-file style listing) """ import sys from itertools import combinations # ---------------------------------------------------------------------------- # Definitions (paper, Section 1) # ---------------------------------------------------------------------------- def profile(edges): """Attachment profile pi(G) = (i, p, f) of a graph given as a list of edges. An edge contributes to i, p or f according to whether 0, 1 or 2 of its endpoints have degree > 1. """ deg = {} for u, v in edges: deg[u] = deg.get(u, 0) + 1 deg[v] = deg.get(v, 0) + 1 i = p = f = 0 for u, v in edges: a = (deg[u] >= 2) + (deg[v] >= 2) if a == 0: i += 1 elif a == 1: p += 1 else: f += 1 return (i, p, f) # ---------------------------------------------------------------------------- # The Edge Growth Automaton (paper, Section 4.1) # ---------------------------------------------------------------------------- RULES = ('R1', 'R2', 'R3', 'R4', 'R5') def successors(state, rules=RULES): """States reachable from `state` by one application of any enabled rule.""" i, p, f = state out = [] if 'R1' in rules: out.append((i + 1, p, f)) if 'R2' in rules and (p > 0 or f > 0): out.append((i, p + 1, f)) if 'R3' in rules and i > 0: out.append((i - 1, p + 2, f)) if 'R4' in rules and p > 1: out.append((i, p, f + 1)) if 'R5' in rules and p >= 2: out.append((i, p - 2, f + 3)) return out def automaton(N, rules=RULES): """R_n for n = 1..N, as a dict n -> set of states.""" level = {(1, 0, 0)} out = {1: set(level)} for n in range(1, N): nxt = set() for s in level: nxt.update(successors(s, rules)) level = {s for s in nxt if min(s) >= 0} out[n + 1] = set(level) return out # ---------------------------------------------------------------------------- # Achievable profiles, from the structure theorem (paper, Section 2) # ---------------------------------------------------------------------------- def connected_splits(k): """C_k, the (p, f) pairs realized by connected graphs with k edges (Lemma 2).""" if k == 1: return {(0, 0)} # handled as an i-edge if k == 2: return {(2, 0)} if k == 3: return {(3, 0), (2, 1), (0, 3)} return {(k - f, f) for f in range(k + 1)} def achievable(N): """P(n) for n = 1..N by component decomposition (Lemma 1).""" reach = {0: {(0, 0, 0)}} for total in range(1, N + 1): acc = set() for k in range(1, total + 1): comps = [(1, 0, 0)] if k == 1 else [(0, p, f) for (p, f) in connected_splits(k)] for (i0, p0, f0) in comps: for (i, p, f) in reach[total - k]: acc.add((i + i0, p + p0, f + f0)) reach[total] = acc return {n: reach[n] for n in range(1, N + 1)} def excluded(n): """The five profiles Theorem 1 rules out, for n >= 3.""" return {(n - 1, 1, 0), (n - 1, 0, 1), (n - 2, 1, 1), (n - 2, 0, 2), (n - 3, 1, 2)} def all_triples(n): return {(a, b, n - a - b) for a in range(n + 1) for b in range(n - a + 1)} def S(n): """Closed form, Corollary 1.""" if n == 1: return 1 if n == 2: return 2 return (n + 2) * (n + 1) // 2 - 5 # ---------------------------------------------------------------------------- # Exhaustive graph enumeration (ground truth) # ---------------------------------------------------------------------------- def connected(m, edges): adj = {x: set() for x in range(m)} for u, v in edges: adj[u].add(v); adj[v].add(u) seen = {edges[0][0]} stack = [edges[0][0]] while stack: x = stack.pop() for y in adj[x]: if y not in seen: seen.add(y); stack.append(y) return len(seen) == len({x for e in edges for x in e}) def connected_splits_bruteforce(k): """C_k computed by enumerating every connected graph with k edges.""" found = set() for m in range(2, k + 2): # <= k+1 vertices if connected pool = list(combinations(range(m), 2)) if len(pool) < k: continue for es in combinations(pool, k): deg = [0] * m for u, v in es: deg[u] += 1; deg[v] += 1 if any(d == 0 for d in deg): # every vertex used continue if not connected(m, es): continue _, p, f = profile(es) found.add((p, f)) return found def build_witness(p, f): """The Lemma 2 constructions, as explicit edge lists.""" k = p + f if f == 0: return [(0, j) for j in range(1, k + 1)] # star K_{1,k} if f == 1: a = (p + 1) // 2; b = p - a return ([(0, 1)] + [(0, 100 + j) for j in range(a)] + [(1, 200 + j) for j in range(b)]) # two stars joined if f == 2: a = (p + 1) // 2; b = p - a return ([(0, 1), (1, 2)] + [(0, 100 + j) for j in range(a)] + [(2, 200 + j) for j in range(b)])# path with pendants return ([(j, (j + 1) % f) for j in range(f)] + [(j % f, 100 + j) for j in range(p)]) # cycle with pendants def relabel(edges): vs = sorted({x for e in edges for x in e}) ix = {v: i for i, v in enumerate(vs)} return len(vs), [(ix[u], ix[v]) for u, v in edges] # ---------------------------------------------------------------------------- # Checks # ---------------------------------------------------------------------------- RESULTS = [] def check(label, ok, detail=''): RESULTS.append(ok) print(f" [{'PASS' if ok else 'FAIL'}] {label}" + (f" {detail}" if detail else '')) return ok def main(): full = '--full' in sys.argv if '--terms' in sys.argv: for n in range(1, 51): print(n, S(n)) return 0 print(__doc__.split('\n')[2].strip()) print() # --- Lemma 2 ------------------------------------------------------------- print("Lemma 2 — connected profiles") kmax = 7 if full else 6 ok = True for k in range(2, kmax + 1): got = connected_splits_bruteforce(k) ok &= (got == connected_splits(k)) check(f"exhaustive enumeration of connected graphs, k = 2..{kmax}", ok) ok = True for k in range(4, 31): for f in range(k + 1): p = k - f m, es = relabel(build_witness(p, f)) distinct = len({tuple(sorted(e)) for e in es}) == k ok &= distinct and connected(m, es) and profile(es) == (0, p, f) check("explicit constructions realize every split, k = 4..30", ok) # --- Theorem 1 ----------------------------------------------------------- print("\nTheorem 1 — characterization") P = achievable(30) ok = all(P[n] == all_triples(n) - excluded(n) for n in range(3, 31)) check("P(n) equals all triples minus the five excluded, n = 3..30", ok) if full: # Independent ground truth: enumerate EVERY graph with n edges directly, # bypassing Lemmas 1 and 2 entirely. A graph with n edges spans at most # 2n vertices (n disjoint edges), so the vertex bound must be 2n, not n+1. gp = {} for n in range(1, 6): pool = list(combinations(range(2 * n), 2)) gp[n] = {profile(es) for es in combinations(pool, n)} ok = all(gp[n] == P[n] for n in range(1, 6)) check("direct enumeration of every graph, n = 1..5 (all vertex counts)", ok) # --- Corollary 1 --------------------------------------------------------- print("\nCorollary 1 — counting") ok = all(len(P[n]) == S(n) for n in range(1, 31)) check("|P(n)| = C(n+2,2) - 5 for n >= 3, n = 1..30", ok) ok = all(S(n) == S(n - 1) + n + 1 for n in range(4, 200)) check("recurrence S(n) = S(n-1) + n + 1, n = 4..199", ok) # --- Corollary 2 / A052905 ---------------------------------------------- A052905 = lambda m: (m * m + 7 * m + 2) // 2 ok = all(S(n) == A052905(n - 2) for n in range(3, 41)) check("S(n) = A052905(n-2), n = 3..40", ok) # --- Theorem 2 ----------------------------------------------------------- print("\nTheorem 2 — soundness and completeness") R = automaton(201) ok = all(R[n] == all_triples(n) - excluded(n) for n in range(3, 202)) check("automaton reachability matches Theorem 1, n = 3..201", ok) ok = all(R[n] == P[n] for n in range(1, 25)) check("R_n = P(n) as SETS (not merely counts), n = 1..24", ok) # --- Proposition 1 ------------------------------------------------------- print("\nProposition 1 — minimality") witnesses = {'R1': (2, 0, 0), 'R2': (0, 3, 0), 'R3': (0, 2, 0), 'R4': (0, 2, 1), 'R5': (0, 0, 3)} ok = True for r, w in witnesses.items(): n = sum(w) without = automaton(12, tuple(x for x in RULES if x != r)) ok &= (w in R[n]) and (w not in without[n]) check("each rule has a witness unreachable without it", ok, ' ' + ', '.join(f"{r}:{w}" for r, w in witnesses.items())) # --- Section 5 ----------------------------------------------------------- print("\nSection 5 — the unsound rule") def with_bad(N): level = {(1, 0, 0)}; out = {1: set(level)} for n in range(1, N): nxt = set() for s in level: nxt.update(successors(s)) i, p, f = s if p > 0: nxt.add((i, p - 1, f + 2)) # the rule the paper rejects level = {s for s in nxt if min(s) >= 0} out[n + 1] = set(level) return out B = with_bad(25) ok = all(B[n] - R[n] == {(n - 3, 1, 2)} for n in range(4, 25)) check("adding 'convert p->f' contributes exactly (n-3,1,2), n = 4..24", ok) ok = all(len(B[n]) == len(R[n]) + 1 for n in range(4, 25)) check("...and so inflates the count by exactly one per level", ok) # --- Summary ------------------------------------------------------------- print("\n" + "-" * 62) print(f"{sum(RESULTS)}/{len(RESULTS)} checks passed" + ("" if all(RESULTS) else " *** SOME CHECKS FAILED ***")) print("\nSequence, n = 1..24:") print(" " + ", ".join(str(S(n)) for n in range(1, 25))) return 0 if all(RESULTS) else 1 if __name__ == '__main__': sys.exit(main()) # ---------------------------------------------------------------------------- # License # ---------------------------------------------------------------------------- # # (c) 2026 Brian Klemm. Licensed under Creative Commons # Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0): # https://creativecommons.org/licenses/by-nc-nd/4.0/ # # Share it anywhere you like, whole and unaltered, with credit to the author. # Commercial use and derivative versions require written permission -- # brian@brianklemm.com.