Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees

@misc{aichholzer2026counterexamples,
  title = {{Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees}},
  author = {Oswin Aichholzer and Joseph Dorfer and Peter Kramer and Christian Rieck and Birgit Vogtenhuber},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05300},
  eprint = {2611.05300},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05300},
}

TY  - UNPB
TI  - Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees
AU  - Oswin Aichholzer
AU  - Joseph Dorfer
AU  - Peter Kramer
AU  - Christian Rieck
AU  - Birgit Vogtenhuber
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05300
UR  - https://arxiv.org/abs/2611.05300
AB  - 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 up to 10 points in convex position. In this paper, we disprove this conjecture both on general point sets and on point sets in convex position by providing two counterexamples on $16$ and $30$ points, respectively. The counterexample for point sets in general position also holds for compatible flips, while the happy edge property holds for compatible flips in convex point sets as shown by Aichholzer, Dorfer, and Vogtenhuber [GD 2025].
ER  -