The weak happy edge conjecture for plane spanning trees
Let be a convex point set, and let and be plane spanning trees on . An edge is happy if it belongs to both and . Weak happy edge conjecture. There is a shortest flip sequence from to that does not flip happy edges. This conjecture asks whether shortest reconfiguration sequences can preserve all edges common to the initial and target trees. Its resolution is not given in the supplied text.
References
- Oswin Aichholzer, Joseph Dorfer and Birgit Vogtenhuber, “Constrained Flips in Plane Spanning Trees”, arXiv:2508.15520 (2025).
Progress summary
A November 2026 preprint claims a counterexample disproving the conjecture, but the claim has not been independently verified.
The conjecture asks whether some shortest flip sequence between two plane spanning trees can preserve every edge they share. The new preprint claims this fails even for convex point sets.
Known results
- For compatible flips on convex point sets, the conjecture is reported to hold (Aichholzer, Dorfer, Kramer, Rieck, and Vogtenhuber, 2025).
November 2026 counterexample
Aichholzer, Dorfer, Kramer, Rieck, and Vogtenhuber claim two plane spanning trees on points in convex position with unrestricted flip distance , while preserving all happy edges requires at least flips. They also give a -point general-position example with distances and . The preprint reports these as AI-assisted discoveries, but no independent mathematical assessment was found.
Current status (as of November 2026): The unrestricted conjecture is claimed disproved by explicit counterexamples, while the compatible-flip variant is reported true; the counterexamples remain unverified.
Sources
Solutions 0
No solutions have been posted yet.