← All problems

The weak happy edge conjecture for plane spanning trees

1 year old · traced to

Let SS be a convex point set, and let TinT_{\text{in}} and TtarT_{\text{tar}} be plane spanning trees on SS. An edge is happy if it belongs to both TinT_{\text{in}} and TtarT_{\text{tar}}. Weak happy edge conjecture. There is a shortest flip sequence from TinT_{\text{in}} to TtarT_{\text{tar}} 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
  1. Oswin Aichholzer, Joseph Dorfer and Birgit Vogtenhuber, “Constrained Flips in Plane Spanning Trees”, arXiv:2508.15520 (2025).

Progress summary

Refreshed
Open · solution reported

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 3030 points in convex position with unrestricted flip distance 1919, while preserving all happy edges requires at least 2020 flips. They also give a 1616-point general-position example with distances 1212 and 1313. 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.