Written on the Wall IICombinatorics
Written on the Wall II - Conjecture 141
WOWII Conjecture 141
Mathematical statement
WOWII Conjecture 141
For a simple connected graph G,
tree(G) ≥ ⌊girth(G) / 2⌋ - 1 + max_v l(v)
where tree(G) is the number of vertices of a largest induced tree subgraph,
girth(G) is the length of the shortest cycle (0 if acyclic), and
l(v) = indepNeighbors G v is the independence number of the neighbourhood of v.
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
conjecture141
theorem conjecture141 (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) : (G.girth / 2 : ℤ) - 1 + ((Finset.univ.sup (indepNeighborsCard G) : ℕ) : ℤ) ≤ (largestInducedTreeSize G : ℤ) := 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