Written on the Wall IICombinatorics
Written on the Wall II - Conjecture 200
WOWII Conjecture 200
Mathematical statement
WOWII Conjecture 200
For a simple connected graph G, if tree(G) = ⌈1 + l_avg(G)⌉, then G has a Hamiltonian path.
Here tree(G) is the number of vertices of a largest induced tree subgraph, and
l_avg(G) = averageIndepNeighbors G is the average over all vertices of the independence number
of the neighbourhood.
A Hamiltonian path is a walk visiting every vertex exactly once.
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
conjecture200
theorem conjecture200 (G : SimpleGraph α) (h : G.Connected) (htree : (largestInducedTreeSize G : ℝ) = ⌈1 + averageIndepNeighbors G⌉) : ∃ a b : α, ∃ p : G.Walk a b, p.IsHamiltonian := 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