Written on the Wall II, Graph Conjecture 2

For a finite connected graph $G$, let $L_s(G)$ be the maximum number of leaves in a spanning tree and $\ell(G)$ the average local independence number. Must $L_s(G) \ge 2(\ell(G) - 1)$?

Result

Proved

Status

Resolved

AI contribution

AI-discovered

Method

Argument

Field

Extremal graph theory

Posed by

Graffiti (Written on the Wall II)

Year posed

1996

Years open

30y

Solved

2026-05-21

Model

AlphaProof Nexus

Vendor

Google DeepMind

Collaborators

—

Verification

Lean-verified

Publication

Preprint

Significance

5 / 100*

Disclosed cost

—

Wikipedia

No dedicated article