Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Graph theory P-wall-graph-conjecture100

Written on the Wall II - Conjecture 100

WOWII Conjecture 100 (status O): For a simple connected graph G, α(G) ≤ ⌈(max_v l(v) + 0.5 · degreeL2Norm(Gᶜ)) / 2⌉ where α(G) = G.indepNum is the independence number, max_v l(v) is the maximum over all vertices of the independence number of the neighbourhood (in G), and degreeL2Norm(Gᶜ) is the…

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-wall-graph-conjecture100,
  title        = {Written on the Wall II - Conjecture 100},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/wall-graph-conjecture100}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

WOWII [Conjecture 100](http://cms.uhd.edu/faculty/delavinae/research/wowII/all.html#conj100) (status O):

For a simple connected graph G, α(G) ≤ ⌈(max_v l(v) + 0.5 · degreeL2Norm(Gᶜ)) / 2⌉ where α(G) = G.indepNum is the independence number, max_v l(v) is the maximum over all vertices of the independence number of the neighbourhood (in G), and degreeL2Norm(Gᶜ) is the square root of the sum of the squares of the degrees in the complement Gᶜ.

Verbatim statement (WOWII #100, status O): > If G is a simple connected graph, then α(G) ≤ CEIL[(maximum of λ(v) + 0.5*length(Ḡ))/2]

Source: http://cms.uhd.edu/faculty/delavinae/research/wowII/all.html#conj100

The WOWII HTML uses length(Ḡ) (the bar denotes graph complement); the extracted JSON in our private repo previously dropped the overline. The formal statement below uses the Euclidean norm of the degree sequence of Gᶜ.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.WrittenOnTheWallII.GraphConjecture100.

theorem conjecture100 (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) :
    let maxL := (Finset.univ.image (indepNeighborsCard G)).max' (by simp)
    (G.indepNum : ℝ) ≤ ⌈((maxL : ℝ) + (1 / 2) * (degreeL2Norm Gᶜ : ℝ)) / 2⌉

What counts as progress

  • A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

[E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/)

Definition of graph length

The WOWII definitions popup defines length(H) as the square root of the sum of the squares of the vertex degrees. This is degreeL2Norm H in Lean. Combined with the overline above, the inequality reads: α(G) ≤ ⌈(max_v l(v) + 0.5 · degreeL2Norm(Gᶜ)) / 2⌉ where l(v) = indepNeighbors G v.

Source and licence

Imported from Formal Conjectures (Written on the Wall II), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.