2026/07/27 by Yanmohan Wang, Tianyue Dai, Rui Tong
#math.CO
We prove Graffiti.pc Conjecture 2, a 1996 conjecture listed as open on the Written on the Wall II page marked ``Last update 7/23/26.'' Let G be a finite simple connected graph. For v∈ V(G), let I(v)=α(G[NG(v)]), and let Iavg(G) be the average of these local independence numbers. The conjecture states that the maximum number Ls(G) of leaves in a spanning tree of G satisfies Ls(G)≥ 2(Iavg(G)-1). We establish this inequality by extracting a triangle-free spanning subgraph that retains at least half of the total local-independence mass. A degree-square argument then produces a double star with sufficiently many leaves, and this tree extends to a spanning tree without losing leaves. Balanced complete bipartite graphs show that the bound is sharp.