Which Pairs of Forbidden Subgraphs Force Every Maximal Matching to Be Maximum?

A matching is a set of edges that share no vertices. A graph is equimatchable if the simplest greedy procedure, adding edges until no more fit, always ends with a largest possible matching. Graph theorists have long described classes of graphs by listing small patterns that may not appear as induced subgraphs: a vertex subset together with every edge the graph has among those vertices. A classical example of this style is that forbidding the claw (one vertex joined to three mutually non-adjacent vertices) guarantees a perfect matching in connected graphs of even order. A pair of forbidden subgraphs and perfect matchings extended this to pairs of forbidden graphs and settled which pairs force a perfect or near-perfect matching. That paper, however, only asks whether one good matching exists. It says nothing about when every greedy matching is optimal, which is a much stronger property.

This note proposes to settle the equimatchability version of that question: which pairs $\{H_1, H_2\}$ have the property that every sufficiently large connected graph containing neither $H_1$ nor $H_2$ as an induced subgraph is equimatchable. The approach rests on a local fact about how a greedy matching fails. Whenever a maximal matching is not maximum, some maximal matching has an edge $ab$ with two unmatched vertices hanging off it, one attached to $a$ and one attached to $b$. This "dual-endpoint" witness always induces one of three four-vertex graphs. That turns a global matching property into a local pattern that forbidden-subgraph arguments can control.

Core Claim

The main technical lever is a short lemma. A graph $G$ is not equimatchable if and only if there is a maximal matching $M$, an edge $ab \in M$, and two vertices $u, w$ left unmatched by $M$ with $u$ adjacent to $a$ and $w$ adjacent to $b$. Equivalently, the path $u$–$a$–$b$–$w$ can be used to enlarge $M$; it is an augmenting path of length 3.

The proof sketch runs as follows. Among maximal but non-maximum matchings, pick one whose shortest augmenting path $u, a_1, b_1, a_2, \dots, w$ is as short as possible, and suppose that length exceeds 3. Swap $a_1b_1$ for $ua_1$. The vertex $b_1$ becomes unmatched but has no unmatched neighbour. If it had one, say $z$, then $z$–$b_1$–$a_1$–$u$ would already have been an augmenting path of length 3. So the new matching is still maximal and has the same size, yet it has a strictly shorter augmenting path starting at $b_1$, which is a contradiction.

Because $u$ and $w$ are non-adjacent (maximality), the witness $\{u, a, b, w\}$ induces exactly one of three graphs. It is the path $P_4$ if there are no extra edges, the paw (a triangle with a pendant edge) if one extra edge $ub$ or $aw$ is present, and the diamond ($K_4$ minus an edge) if both are present.

Two consequences frame the project. First, the naive "hereditary" version of the question collapses. The graphs all of whose induced subgraphs are equimatchable are exactly the $\{P_4, \text{paw}, \text{diamond}\}$-free graphs. Using the standard fact that paw-free cographs have complete-multipartite or triangle-free components, these are precisely disjoint unions of cliques and complete bipartite graphs. This is a one-page result and not the target. It shows why the interesting question is the non-hereditary one: equimatchability is forced by a forbidden family inside a larger hereditary class, exactly as perfect matchings are in the Fujita-style setting. Second, the witness lemma gives a certificate-producing, polynomial-time test for non-equimatchability. For each edge $ab$ and each candidate non-adjacent pair $u \sim a$, $w \sim b$, ask whether $G - \{u, w\}$ has a matching containing $ab$ that covers every neighbour of $u$ and $w$. Asking whether a matching covers a prescribed vertex set is a standard polynomial matching question.

The central claim is that the list of forcing pairs is finite and short, and can be pinned down by a two-sided method. On the necessity side, explicit infinite families of connected non-equimatchable graphs restrict the candidates. One member of every forcing pair must be an induced path, because long paths $P_n$ are connected and non-equimatchable. The other member must be an induced subgraph of every large connected non-equimatchable graph that avoids that path. Two such families are already visible, and both are claw-free and $P_5$-free. The first is a vertex joined to an isolated vertex and to a clique of even order $2m$. The second is an even clique $K_{2m}$ with a pendant path of length two. On the sufficiency side, the witness lemma reduces each proof to showing that, in a large connected $\{H_1,H_2\}$-free graph, no dual-endpoint witness can sit inside a maximal matching.

Research Program

The first stage builds the necessity side. We will construct a catalogue of infinite families of connected non-equimatchable graphs, organised by which of $P_4$, paw and diamond their witnesses induce and by the long-range structure around them: paths, clique-with-pendant gadgets, complete bipartite graphs with attachments, and joins. The pairs that survive are those in which each family eventually avoids neither $H_1$ nor $H_2$. Intersecting the induced-subgraph posets of these families, following the poset formalism of A pair of forbidden subgraphs and perfect matchings, gives a finite candidate set.

The second stage is computational triage. For every candidate pair, exhaustive enumeration finds the largest connected $\{H_1,H_2\}$-free non-equimatchable graph up to a size limit. A pair whose counterexamples keep growing is eliminated, and the counterexamples usually suggest a new infinite family to feed back into stage one. A pair whose counterexamples stop at some order $n_0$ becomes a conjecture with an explicit exceptional list.

The third stage proves sufficiency for the surviving pairs. The proofs will use the witness lemma, a Ramsey-type argument (large connected graphs forbidding a path and a small graph contain a large clique or a large induced star-like structure), and the homogeneous-set style of case analysis used for finiteness of critical graphs in Some Results on Critical (P5,H)-free Graphs.

A fourth, conditional stage asks the same question under a connectivity assumption. The aim is to place Equimatchable factor-critical graphs and independence number 2 inside the new picture. That paper shows that, for $k \ge 4$ and cut components of size at least 3, equimatchable factor-critical graphs are exactly those with no three mutually non-adjacent vertices (induced-$3K_1$-free). It also shows that the equivalence needs an extra edge-addition condition at connectivity 2. Our framework asks which pairs force equimatchability among 2- and 3-connected graphs. That is exactly the regime where their single-graph criterion breaks down.

We deliberately set aside the tight and anti-tight graphs of On Tight Components and Anti-Tight Components. The definitions as summarised in our file are inconsistent with the stated theorem: odd cliques are called tight, yet "exactly one endpoint" adjacency fails in cliques. Building on them would require recovering the precise definition first. Equimatchability has an unambiguous definition, and it has a documented gap left open by the forbidden-pair literature.

Baselines

The naive reference point is the trivial single-graph answer. A connected graph with no induced $P_3$ is complete and hence equimatchable, and the hereditary closure computed above gives the $\{P_4,\text{paw},\text{diamond}\}$-free class. Any forcing pair we find must describe a strictly larger class than these, for example one containing large connected graphs that have induced $P_4$ or paws. We will certify this by exhibiting infinite families inside each $\{H_1,H_2\}$-free class that are equimatchable but not unions of cliques and bicliques.

The strongest existing competitor is the pair classification in A pair of forbidden subgraphs and perfect matchings. It identifies which pairs force perfect matchings (any such pair reduces to a single graph below the claw) and which force near-perfect matchings in odd graphs, including $\{K_{1,4}, P_4\}$ and $\{K_{1,4}, \text{chair}\}$. It is the closest method and the natural suspect: one might guess that the pairs forcing a good matching also force every greedy matching to be good. The fair comparison runs each of their pairs through the same enumeration pipeline and the same size limits as our candidates. The paper reports no numerical metric; its result is the pair list itself. We found no reported result on Lacuna for pairs forcing equimatchability. Beating this baseline means showing that the equimatchability list is a strict and differently shaped refinement of theirs. Concretely, at least one of their near-perfect pairs admits infinitely many connected non-equimatchable graphs, and at least one of our forcing pairs does not appear in their list.

A second structural baseline is the independence-number criterion of Equimatchable factor-critical graphs and independence number 2. We will measure, on the same enumerated graphs split by connectivity, how often induced-$3K_1$-freeness agrees with equimatchability. The comparison is at the level of agreement rates, not a published accuracy; no such rate is reported in the file.

The ablation that isolates the key ingredient removes the witness lemma. In one version, sufficiency is attempted by reasoning about arbitrary augmenting paths. In the other, it is attempted with the lemma's reduction to length-3 witnesses. Computationally, the same ablation compares a checker that enumerates all maximal matchings against the witness-based checker, on agreement and on running time as graph order grows.

Why not just…?

Why not just use the Gallai–Edmonds decomposition, which already describes all maximum matchings? It describes the structure but does not yield short criteria. The authors of On two equimatchable graph classes describe earlier decomposition-based characterizations as offering little structural insight, and their planar proof as long. Equimatchable factor-critical graphs and independence number 2 stalls when cut components are singletons. The decomposition will still be a tool inside sufficiency proofs. The deliverable here is a forbidden-pattern statement that the decomposition does not produce by itself.

Why not just forbid three mutually non-adjacent vertices, since independence number 2 already characterises equimatchable factor-critical graphs? That equivalence needs connectivity at least 4 and large cut components. Without those conditions it fails outright: $P_4$ has independence number 2 and is not equimatchable. The connectivity-split agreement experiment will quantify how quickly the criterion degrades below connectivity 4.

Why not just take the claw-free and near-perfect-matching pairs already known? Both necessity families above are claw-free and non-equimatchable, as is the paw itself. So claw-freeness cannot force equimatchability, and the known pairs guarantee existence, not greediness. Running their pairs through our pipeline is the direct test.

Why not just search by computer and stop there? This is the real threat to the proof effort, since enumeration will find the candidate list quickly. But enumeration only reaches about ten vertices, while "every sufficiently large graph" is a statement about all orders. Search cannot distinguish an exceptional list that truly ends from a family that resumes beyond the search limit. The proposal uses search to prune and to suggest families. Only the witness-lemma proofs close the question, and any pair whose proof fails stays labelled a conjecture.

Proposed Experiments

The first experiment validates the pipeline. The witness-based equimatchability checker must reproduce the published classifications: exactly 23 3-connected planar equimatchable graphs (one on 4 vertices, two on 5, nineteen on 7, one on 9) and exactly two connected cubic equimatchable graphs, $K_4$ and $K_{3,3}$, both from On two equimatchable graph classes. The code that filters graphs by forbidden induced subgraphs is validated separately. It must reproduce the reported count of 344 five-vertex-critical $(P_5, K_{1,3}+P_1)$-free graphs from Some Results on Critical (P5,H)-free Graphs, using the same criticality definition. We also verify the witness lemma itself by checking agreement against brute-force enumeration of maximal matchings on all connected graphs up to ten vertices. A single disagreement would falsify our proof sketch and halt the program.

The second experiment is the triage. For all pairs of connected graphs on at most five vertices, including every pair from the Fujita-style classification, we record the largest order at which a connected $\{H_1,H_2\}$-free non-equimatchable graph exists. The enumeration covers all connected graphs up to ten vertices, and restricted generation inside each $\{H_1,H_2\}$-free class reaches beyond that. The decisive observable is whether the counterexample order stabilises. The prediction to be tested is that every surviving pair contains an induced path, and that the second member lies in the common induced-subgraph poset of the two clique-with-pendant families.

The third experiment is the connectivity split. We compare induced-$3K_1$-freeness with equimatchability on 2-, 3- and 4-connected odd graphs, reporting agreement by connectivity. This locates exactly where the Eiben–Kotrbčík criterion stops working and which second forbidden graph repairs it.

The project succeeds if it delivers three things: a proven, finite list of forcing pairs with explicit exceptional graphs; a demonstration that this list differs from the perfect-matching list; and the witness-lemma checker as a reusable certificate tool. It fails informatively if some candidate pair resists both proof and counterexample. That outcome would identify a concrete open conjecture at the point where the local witness no longer controls global structure.