The ordered graph
Available Selected matching Deleted
Tap or click two vertices to select or unselect their edge. The vertex menus above do the same.
Start with six vertices
Crossing is allowed. Nesting is not.
Choose disjoint pairs in the same graph. The thin edges remain available.
The complete classification · Theorem 2.1
How few deletions stop every perfect matching?
On 2k vertices, exactly k are needed. Explore all three families.
Matchings in this graph
Choose a card to see the matching in the graph.
A checkable answer
Inspect the interval blocks
New in v2 · Coordinated endpoint constructions
Keep more edges, even with unused vertices.
Four deletion regions work together. Inspect them in the matrix and the graph.
Where the deletions lie
row x · column yEach cell is one edge {x, y}, with x < y. Tap or click a cell to inspect it; the Vertex x and Vertex y menus give the same inspection.
Large squares, fixed row and column numbers, and vertex menus.
The deleted edges
Dashed: deleted. Dark solid: inspected edge. Teal: selected witness.
Why the triangle matters
One restored edge opens a way through.
The 19-vertex example needs the edge {2, 13} deleted. Restore it to reveal eight permitted pairs.
Construction certificate
Four disjoint regions, one blocker
The excess
A lower bound on the unknown optimum
“Best” optimizes the parameters of Theorem 4.5 only. The exact extremal value is open in general.
Definitions, controls and scope
A matching uses each vertex at most once. Order its edges by their smaller endpoints. It is nonnested exactly when the larger endpoints also increase. Crossings are permitted. Unselected edges do not affect this test.
A blocker meets every target matching in an edge. A minimum blocker has the smallest number of deletions; this is stronger than being inclusion-minimal. The classification is for perfect matchings on exactly 2k vertices.
Undo and Redo restore the active tab, graph, selection and applied construction parameters (up to 80 actions). Reset tab is undoable. During the guide it resets only the current guide step. A guide started from your exploration saves your graph, selection, target, construction and collection view; Explore freely restores them. You can instead keep the guide graph. Collection pages contain six cards and always identify their shown range and full count. Action modes and inspection are view choices; they do not add Undo entries. Actions that change nothing, such as choosing the matching already shown, add no Undo step. Display filters and edge inspections do not change the graph. Counts cancel when the graph changes.
Exact enumeration runs separately from Algorithm 1, in a cancelable worker, with a limit of 2,000,000 target patterns and k ≤ 9. Larger constructions use the theorem under its checked hypotheses. The edge matrix here is not the permutation-matrix embedding in Proposition 3.3.