Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees

Source: arxiv.org/abs/2611.05300

Oswin Aichholzer, Joseph Dorfer, Peter Kramer, Christian Rieck, Birgit Vogtenhuber

arXivarxiv/2611.05300Nov 3, 2026cs.CGscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.05300
curl -X POST /api/v1/records/arxiv/2611.05300/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05300/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'