The happy-edge conjecture for convex plane spanning trees
Let $P \subset \mathbb{R}^2$ be a finite set in strictly convex position. A plane spanning tree on $P$ is a spanning tree with vertex set $P$ whose edges are straight segments, no two crossing. A flip removes one edge and inserts another so that the result is again a plane spanning tree; the removed and inserted edges may cross. The edges in $E(T) \cap E(T')$ are the happy edges of $T$ and $T'$.
Aichholzer, Ballinger, Biedl, Damian, Demaine, Hesterberg, Korman, Lubiw, Lynch, Tkadlec and Uno proved that every shortest flip sequence keeps the happy edges on the boundary of the convex hull, checked by computer that the property in the problem holds for $|P| \le 10$, and showed that its analogue for edge slides fails. Aichholzer, Dorfer and Vogtenhuber proved that for compatible flips, in which the removed and inserted edges do not cross, no shortest sequence of compatible flips removes a happy edge, and that the analogue for rotations fails. Bjerkevik, Kleist, Ueckerdt and Vogtenhuber constructed, for $|P| \ge 3$ and every pair of trees, a flip sequence of length at most $\tfrac53 |E(T) \setminus E(T')| + \tfrac23 b - \tfrac43$ that flips no happy edge, where $b$ is the number of happy edges on the boundary of the convex hull.
Problem. Prove or disprove that for any two plane spanning trees $T$ and $T'$ on $P$ there is a shortest flip sequence $T = T_0, T_1, \ldots, T_k = T'$ with $$E(T) \cap E(T') \subseteq E(T_i) \qquad (0 \le i \le k).$$
Source: Aichholzer, Ballinger, Biedl, Damian, Demaine, Hesterberg, Korman, Lubiw, Lynch, Tkadlec and Uno (2024), the Happy Edge Conjecture (Conjecture 17), stated for convex point sets in the arXiv version (2022); Aichholzer, Dorfer and Vogtenhuber (2025) also credit a personal communication of F. Hurtado (CCCG 2003).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, flip graphs, non-crossing spanning trees
References
@article{aichholzer2024reconfiguration,
author = {Aichholzer, Oswin and Ballinger, Brad and Biedl, Therese and Damian, Mirela and Demaine, Erik D. and Hesterberg, Adam and Korman, Matias and Lubiw, Anna and Lynch, Jayson and Tkadlec, Josef and Uno, Yushi},
title = {Reconfiguration of non-crossing spanning trees},
journal = {J. Comput. Geom.},
volume = {15},
number = {1},
year = {2024},
pages = {224--253},
doi = {10.20382/jocg.v15i1a9},
eprint = {2206.03879},
archivePrefix = {arXiv},
}
@inproceedings{aichholzer2025constrained,
author = {Aichholzer, Oswin and Dorfer, Joseph and Vogtenhuber, Birgit},
title = {Constrained Flips in Plane Spanning Trees},
booktitle = {33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {357},
year = {2025},
pages = {5:1--5:18},
doi = {10.4230/LIPIcs.GD.2025.5},
eprint = {2508.15520},
archivePrefix = {arXiv},
}
@inproceedings{bjerkevik2025flipping,
author = {Bjerkevik, H{\aa}vard Bakke and Kleist, Linda and Ueckerdt, Torsten and Vogtenhuber, Birgit},
title = {Flipping Non-Crossing Spanning Trees},
booktitle = {Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2025},
pages = {2313--2325},
doi = {10.1137/1.9781611978322.77},
eprint = {2410.23809},
archivePrefix = {arXiv},
}
@misc{aichholzer2026structural,
author = {Aichholzer, Oswin and Dorfer, Joseph and Kramer, Peter and Rieck, Christian and Vogtenhuber, Birgit},
title = {Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees},
year = {2026},
eprint = {2603.05205},
archivePrefix = {arXiv},
}
@misc{aim-convex-tree-happy-edges,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The happy-edge conjecture for convex plane spanning trees}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/586-convex-tree-happy-edges.md},
note = {Entry 586 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00853, "The happy-edge conjecture for convex plane spanning trees", clopen.solutions.