Source labels openChecked July 26, 2026

Written on the Wall II - Conjecture 59

Mathematical statement

For a simple connected graph $G$ , the size $f(G)$ of a largest induced forest satisfies $f(G) \ge \lceil \sqrt{\mathrm{residue}(G) \cdot b(G)} \rceil$ , where $\mathrm{residue}(G)$ is the Havel-Hakimi residue (the number of zeros remaining after applying the Havel-Hakimi algorithm to the degree sequence until termination) and $b(G)$ is the size of a largest induced bipartite subgraph.

See: Favaron, Mahéo, Saclé (1991) for the residue; DeLaVina's Graffiti.pc for the conjecture.

Statement source: Written on the Wall II statement material

Statement terms: Source-specific

Source-specific terms. Therefore does not assert reuse rights beyond attributed display.

Statement artifacts, not proofs

These records expose exact Lean propositions and statement-only wrappers. Defining a proposition does not supply a proof of it. A placeholder-bearing target also contains no proof. Elaboration checks syntax and types; it does not certify that a formalization perfectly captures every nuance of the informal problem.

Pinned Lean formulation 1

conjecture59

Canonical source

Complete statement target, proof intentionally absentLean 4

theorem conjecture59 (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) :    ⌈Real.sqrt ((residue G : ℝ) * b G)⌉ ≤ (G.largestInducedForestSize : ℝ) := by  sorry

Statement source: Formal Conjectures
Lean version: v4.27.0
Placeholder: Present; no proof artifact
Source evidence: Pinned source index
Fidelity review: Community formulation

References

Pinned Formal Conjectures sourceformalization Conjecture 59background