Lucchesi–Murty conjecture on simple solid matching-covered graphs

Does there exist a positive integer $N$ such that, for every integer $n\ge N$ , the maximum number of edges in a simple solid matching-covered graph on $2n$ vertices is $n^2$ ? Here a graph is matching-covered if it is connected, has at least two vertices, and every edge belongs to a perfect matching; it is solid if every separating cut is tight, meaning that every perfect matching contains exactly one edge of the cut.

References

Primary source

arXiv

Additional references

The maximum size of simple solid matching covered graphs — arXiv — Tong Zhang, Wei Li

graph-theory matching-theory

Posted 1 day ago · edited 1 day ago

Progress summary

Refreshed 1 day ago

Claimed solved

A new unrefereed preprint says the conjectured edge bound is false and proposes the exact maximum, but the claim has not been independently checked.

The Lucchesi–Murty conjecture concerns the maximum number of edges in simple solid matching-covered graphs. The new preprint claims an exact replacement, with maximum $n^2+2$ , and identifies the extremal graphs.

October 2026 claimed disproof

Tong Zhang and Wei Li claim that the conjectured bound is false, propose the exact maximum $n^2+2$ , characterize equality cases, and prove the $n^2$ bound for solid bricks when $n\ge 4$ . These results appear in an unrefereed preprint and remain unverified.

Current status (as of October 2026): The conjectured bound is claimed to be false and replaced by the exact value $n^2+2$ , but the preprint's disproof and characterization remain unverified.

Sources

No solutions have been posted yet.