Graph Transformer Euler-Path Impossibility — Proof Project

A rigorous separation theorem: standard self-attention without edge information cannot determine whether a graph has an Euler path, while a GT with edge bias can. This is the first impossibility result connecting the Königsberg bridges problem to modern Graph Transformer architectures.

Status

Result	Status	Empirical metric
Theorem 1: Edge-Information Barrier	✅ Proved	1000 graphs, max readout diff = 0.0
Theorem 2: Degree-Only Insufficiency	✅ Proved	10 random inits, permutation + graph diff = 0.0
Theorem 3: Edge-Bias Sufficiency	✅ Proved	200 random graphs, parity logic = 100.0%

File map

graph-transformer-euler-impossibility/
├── README.md            ← you are here
├── THEOREM.md           ← formal statement with notation and 3 theorems
├── proof/proof.md       ← full mathematical proof, lemma by lemma
├── empirical/verify.py  ← heavily-commented PyTorch verification (Jetson GPU)
├── tests/test_project.py ← pytest suite: 13 tests, all passing
├── backlog/             ← sibling proof targets from Pickover's index
│   └── README.md
└── assets/              ← (empty — figures generated on demand)

Quick start

cd ~/projects/graph-transformer-euler-impossibility
source ~/heartlib/.venv/bin/activate
python empirical/verify.py
python -m pytest tests/ -v

What this proves

Theorem 1 is an architectural impossibility result. It shows that if you strip edge information from a Graph Transformer and initialize all node features identically, the model becomes completely blind to graph structure — its readout is identical for every graph of the same size. This is not a "training failure" or "insufficient data"; it is a mathematical consequence of permutation-equivariance + no edge channel.

Theorem 2 shows that even giving the model exact degree features is insufficient, because degree sequences alone cannot distinguish connected graphs from disconnected ones with the same histogram. We prove this with the explicit counterexample C6 (connected) vs two disjoint C3s (disconnected), both with degree sequence [2,2,2,2,2,2].

Theorem 3 is the positive side: once edge bias is added to the attention mechanism, the model has access to the full adjacency structure, and the Euler-path condition (parity of odd-degree vertex count) becomes computable. We verify this with an analytic parity check that is 100% accurate on 200 random connected graphs.

Reproducing the run on the Jetson

Actual output from python empirical/verify.py on Jetson Orin (PyTorch 2.5.0, CUDA 12.6):

======================================================================
 Graph Transformer Euler-Path Impossibility — Empirical Verification
======================================================================
GPU: Orin
Device: cuda
  PyTorch: 2.5.0a0+872d972e41.nv24.08
  CUDA:    12.6

--- Theorem 1: Edge-Information Barrier ---
  ✓  Max readout difference across 1000 graphs: 0.000000e+00 (threshold=0.0001)

--- Theorem 2: Degree-Only Insufficiency ---
  ✓  Max perm_diff=0.00e+00, max graph_diff=0.00e+00 over 10 random inits

--- Theorem 3: Edge-Bias Sufficiency ---
  ✓  Parity logic accuracy: 100.0%, Linear model accuracy: 100.0% (200/200)

======================================================================
SUMMARY: 3/3 theorems verified
   ✓ PASS  Theorem 1: Edge-Information Barrier
   ✓ PASS  Theorem 2: Degree-Only Insufficiency
   ✓ PASS  Theorem 3: Edge-Bias Sufficiency
======================================================================

$ python -m pytest tests/ -v
============================== 13 passed in 3.09s ==============================

Next steps (in priority order)

1. Push to GitHub — git remote add origin ... && git push -u origin master
2. Write up as arXiv preprint — the three theorems + empirical verification form a self-contained 4-page paper
3. Sibling projects — see backlog/README.md for 7 additional proof targets from Pickover's index, all scaffolded under ~/projects/

Citation

If you use this result, cite as:

@misc{gt-euler-impossibility-2026,
  title={What Graph Transformers Cannot Compute: An Euler-Path Impossibility Theorem},
  author={Walker Kirkpatrick and Hermes Agent},
  year={2026},
  howpublished={\url{https://github.com/drwjkirkpatrick-web/graph-transformer-euler-impossibility}}
}