Written on the Wall II, Conjecture 2
For every finite simple connected graph , let denote the neighborhood of , let be the independence number of the subgraph induced by , and define the average local independence by . Let be the maximum number of leaves in a spanning tree of . Then ; equivalently, in the formalized notation, .
References
Source: GitHub
Progress summary
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.