← All problems

Written on the Wall II, Conjecture 2

For every finite simple connected graph G=(V,E)G=(V,E), let NG(v)N_G(v) denote the neighborhood of vv, let α(G[NG(v)])\alpha(G[N_G(v)]) be the independence number of the subgraph induced by NG(v)N_G(v), and define the average local independence by AvgInd⁡(G)=1∣V∣∑v∈Vα(G[NG(v)])\operatorname{AvgInd}(G)=\frac{1}{|V|}\sum_{v\in V}\alpha(G[N_G(v)]). Let Ls(G)L_s(G) be the maximum number of leaves in a spanning tree of GG. Then 2(AvgInd⁡(G)−1)≤Ls(G)2\bigl(\operatorname{AvgInd}(G)-1\bigr)\le L_s(G); equivalently, in the formalized notation, 2(G.averageIndepNeighbors⁡−1)≤G.Ls2\bigl(G.\operatorname{averageIndepNeighbors}-1\bigr)\le G.Ls.

References

Progress summary

Refreshed
Open · solution reported

A machine-checked record and a recent paper claim the conjecture is solved, but required review means the result is not yet settled.

The conjecture asserts a graph-theoretic lower bound relating the maximum number of leaves in a spanning tree to average local independence. A paper identifies this as the long-standing conjecture listed in Written on the Wall II, though it also records a different numbering in a later source.

Recent developments, July–August 2026

  • A paper updated in July 2026 claims a proof via a triangle-free spanning subgraph, a degree-square argument, and extension to a spanning tree; balanced complete bipartite graphs give sharpness.
  • The record explicitly says normal maintainer review remains required.
Sources

Solutions 0

No solutions have been posted yet.