Hamilton paths and cycles in flip graphs of (almost-)perfect matchings
2026-07-06 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a way to change perfect or almost-perfect matchings of graphs by swapping edges, called flips. They look at both abstract graphs (complete or bipartite) and drawings of graphs on points in the plane without crossing edges. They show that in the abstract case, it is always possible to find a path that visits every matching (a Hamilton path) between any two matchings. However, in the geometric case, such paths that visit all matchings do not exist because many matchings are unreachable by flips. For convex point arrangements, they find a large cycle that visits almost all matchings but not all.
graph theoryperfect matchingalmost-perfect matchingflip operationflip graphHamilton pathHamilton cycleHamilton-connectedHamilton-laceablegeometric graph
Authors
Sofia Brenner, Justin Dallant, Linda Kleist, Robert Lauff, Torsten Mütze
Abstract
We consider the set of matchings of a graph and a local change operation, called a flip, between them. In the combinatorial setting, the base graphs are either complete graphs or complete bipartite graphs, and in the geometric setting, the graphs are embedded on point sets in the plane, with the requirement that edges must be drawn as straight lines and must not cross. For base graphs with an even number of vertices, we consider perfect matchings, i.e., all vertices are matched, and for base graphs with an odd number of vertices, we consider almost-perfect matchings, i.e., all but one vertex of the graph are matched. A 2-flip between two perfect matchings exchanges two edges, and a 1-flip between two almost-perfect matchings exchanges one edge. The corresponding flip graph has the set of perfect or almost-perfect matchings as vertices, with pairs of them connected by an edge if they differ in a 2-flip or 1-flip, respectively. In this work, we provide a comprehensive picture of Hamiltonicity properties of these flip graphs. We prove that the flip graphs in the combinatorial setting are Hamilton-connected, i.e., they admit a Hamilton path between any two vertices, or, if the flip graphs are bipartite, we prove that they are Hamilton-laceable, i.e., they admit a Hamilton path between any two vertices from different partition classes. In the geometric setting, we prove that any path in them misses exponentially many vertices, in particular, they have no Hamilton paths or cycles. For points in convex position and almost-perfect matchings under 1-flips, we complement this by constructing a cycle in the flip graph that visits almost all vertices.