Average Local Independence and the Spanning-Tree Leaf Number: A Proof of Graffiti.pc Conjecture 2
We prove Graffiti.pc Conjecture 2, a 1996 conjecture listed as open on the \emph{Written on the Wall II} page marked ``Last update 7/23/26.'' Let $G$ be a finite simple connected graph. For $v\in V(G)$, let $I(v)=α(G[N_G(v)])$, and let $I_{\mathrm{avg}}(G)$ be the average of these local independence numbers. The conjecture states that the maximum number $L_s(G)$ of leaves in a spanning tree of $G$ satisfies $L_s(G)\ge 2\bigl(I_{\mathrm{avg}}(G)-1\bigr)$. We establish this inequality by extracting a triangle-free spanning subgraph that retains at least half of the total local-independence…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.24020
curl -X POST /api/v1/records/arxiv/2607.24020/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.24020/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'