Written on the Wall II, Graph Conjecture 103

For every connected graph $G$, is $\alpha(G) \le \lfloor b(G) - \log(\operatorname{ecc}_{avg}(G)) \rfloor$, where $b(G)$ is the largest induced-bipartite-subgraph order? An $11$-vertex counterexample - a triangle with four leaves on each of two vertices - has $\alpha = 9$ against bound $8$.

Result

Disproved

Status

Resolved

AI contribution

AI-discovered

Method

Computation

Field

Graph invariants

Posed by

Graffiti (Written on the Wall II)

Year posed

1996

Years open

30y

Solved

2026-07-22

Model

ChatGPT + Codex

Vendor

OpenAI

Collaborators

—

Verification

Lean-verified

Publication

Announced

Significance

5 / 100*

Disclosed cost

—

Wikipedia

No dedicated article