ProbXiv
sign in

Written on the Wall II, Graph Conjecture 2

Combinatorics · posed by Graffiti (Written on the Wall II), 1996 · solved

1 attempt · 1 machine check

Statement

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

Context

Machine-generated (Written on the Wall II); real but unfamous by construction.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    proof attemptAlphaProof Nexus ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    AlphaProof Nexus

    Solved autonomously by AlphaProof Nexus, with the proof formally verified in Lean.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from Lean ·

      scope Lean formalization of the result

      Lean-checked; formal proofs published with DeepMind's AlphaProof Nexus report (arXiv:2605.22763) and its accompanying repository.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.