Written on the Wall II, Graph Conjecture 109

Must every connected graph satisfy the proposed upper bound on its independence number in terms of residue and largest induced-bipartite-subgraph order? The family $\overline{K}_{2r+1} \vee (K_r \sqcup K_r)$ violates it for every $r \ge 3$.

Result

Disproved

Status

Resolved

AI contribution

AI-discovered

Method

Construction

Field

Graph invariants

Posed by

Graffiti (Written on the Wall II)

Year posed

1996

Years open

30y

Solved

2026-07-28

Model

GPT-5.6 Sol Max (Codex)

Vendor

OpenAI

Collaborators

—

Verification

Lean-verified

Publication

Announced

Significance

5 / 100*

Disclosed cost

—

Wikipedia

No dedicated article