{"id":"arxiv/2611.05300","url":"https://arxiv.org/abs/2611.05300","tags":["cs.CG","math.CO"],"score":0,"title":"Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees","domain":"cs.CG","source":"arxiv","authors":["Oswin Aichholzer","Joseph Dorfer","Peter Kramer","Christian Rieck","Birgit Vogtenhuber"],"reviews":0,"subject":"cs.CG","summary":"We study the problem of reconfiguring plane, straight-line spanning trees on point sets in the plane. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set $P$, the flip graph has a vertex for each plane spanning tree on $P$, and an edge between any two trees that differ by a single flip. The folklore happy edge conjecture suggests that any edge shared by both the initial and the target tree (a happy edge) is never flipped in a shortest flip sequence. This conjecture was computationally verified for…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}