/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilWritten on the Wall II - Conjecture 430a
Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc
The conjecture is false for the nonuniform clique blow-up of P₇ with blob
orders (1,4,12,19,12,4,1). Its independent domination number is three, its
center-neighborhood independence number is two, and its Caro--Wei sum is less
than two. The claimed inequality therefore becomes 3 ≤ 2.
@[expose] public sectionnamespace WrittenOnTheWallII.GraphConjecture430aopen SimpleGraphThe center of a finite graph.
noncomputable def centerFinset {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) : Finset V := V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph V⊢ Finset V
classical
All goals completed! 🐙
DeLaViña's N(S): the union of open vertex neighborhoods. This may
intersect S.
def setNeighborhood {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : Finset V :=
Finset.univ.filter fun v => ∃ u ∈ S, G.Adj u vThe exact rational Caro--Wei sum.
def caroWei {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] : ℚ :=
∑ v : V, 1 / ((G.degree v + 1 : ℕ) : ℚ)
WOWII Conjecture 430a asked whether every connected graph G of order
greater than three satisfies
i(G) ≤ α(G[N(C)]) + 2 floor(CW(G)-1).
The answer is no, witnessed by a nonuniform P₇ clique blow-up.
@[category research solved, question, AMS 5,
formal_proof using lean4 at "https://github.com/Kuberwastaken/c5-k4/blob/85fff48cdd7cc1f743802320fdc94db14d1f841e/lean/GraphConjecture430a.lean#L1-L390"]
theorem conjecture430a :
¬ ∀ (V : Type) [Fintype V] [DecidableEq V] [Nonempty V]
(G : SimpleGraph V) [DecidableRel G.Adj],
G.Connected → 3 < Fintype.card V →
(G.indepDominationNumber : ℤ) ≤
((G.induce
(setNeighborhood G (centerFinset G) : Set V)).indepNum : ℤ) +
2 * ⌊caroWei G - 1⌋ := ⊢ ¬∀ (V : Type) [inst : Fintype V] [inst_1 : DecidableEq V] [Nonempty V] (G : SimpleGraph V)
[inst_3 : DecidableRel G.Adj],
G.Connected →
3 < Fintype.card V →
↑G.indepDominationNumber ≤ ↑α(induce (↑(setNeighborhood G (centerFinset G))) G) + 2 * ⌊caroWei G - 1⌋
All goals completed! 🐙end WrittenOnTheWallII.GraphConjecture430a