Mkrtchyan–Petrosyan–Vardanyan conjecture on maximum matchings

Mkrtchyan, Petrosyan, and Vardanyan proposed the conjecture in their 2010 work on maximum matchings. It asserts that graphs whose maximum and minimum degrees differ by at most one have a maximum matching whose unsaturated vertices do not share a neighbor.

Known results

• Subcubic graphs, with $2 \le \delta(G) \le \Delta(G) \le 3$, satisfy the conclusion (Mkrtchyan, Petrosyan, and Vardanyan, 2010).
• Picouleau’s counterexample is a simple bipartite graph with $\delta(G)=4$ and $\Delta(G)=5$ (reported by Petrosyan, 2012).
• Further counterexamples cover degree-gap-one graphs with $\Delta(G) \ge 4$ and regular graphs of degree at least $7$ (Petrosyan, 2012).

August 2013 regular-graph update

The later work proves the conclusion for every simple $k$-regular graph and for $k$-regular multigraphs with $k \le 4$. Combined with the counterexamples, it identifies the $5$- and $6$-regular multigraph cases as the remaining unresolved cases in that account; no later resolution was found in the supplied scan.

Current status (as of September 2026): The general conjecture is refuted by Picouleau’s counterexample; simple regular graphs are settled positively and regular multigraphs of degree at least $7$ negatively, while no resolution of the $5$- or $6$-regular multigraph cases was found.