Written on the Wall II, Graph Conjecture 143

For every finite connected graph, is $\operatorname{girth}(G) + 1$ at most the product of its largest induced-tree order and its second-smallest degree?

Result

Proved

Status

Resolved

AI contribution

AI-discovered

Method

Argument

Field

Graph invariants

Posed by

Graffiti (Written on the Wall II)

Year posed

1996

Years open

30y

Solved

2026-07-21

Model

GPT-5.6 Thinking

Vendor

OpenAI

Collaborators

—

Verification

Lean-verified

Publication

Announced

Significance

5 / 100*

Disclosed cost

—

Wikipedia

No dedicated article