Back to Problems

conjecture4

Specification

WOWII [Conjecture 4](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/) If `G` is a connected graph then the maximum number of leaves over all spanning trees satisfies `Ls(G) ≥ NG(G) - 1` where `NG(G)` is the minimal neighbourhood size of a non-edge of `G`.

Actions

Submit a Proof

Have a proof attempt? Submit it for zero-trust verification.

Submit Proof
Lean 4 Statement 
theorem conjecture4 (G : SimpleGraph α) [DecidableRel G.Adj] [Nontrivial α] (h_conn : G.Connected) :
    NG G - 1 ≤ Ls G
ID: WrittenOnTheWallII__GraphConjecture4__conjecture4
Browse 300 unsolved math conjectures formalized in Lean 4
Browse

All Problems

Explore all 300 unsolved conjectures.

View problems →
ASI Prize documentation for formal verification pipeline
Docs

Verification Pipeline

How zero-trust verification works.

Read docs →
Evaluation Results

Recent Submissions

No submissions yet. Be the first to attempt this problem.