On maximum matchings in almost regular graphs

Abstract

In 2010, Mkrtchyan, Petrosyan and Vardanyan proved that every graph $G$ with $2\le \delta (G)\le \Delta (G)\le 3$ contains a maximum matching whose unsaturated vertices do not have a common neighbor, where $\Delta (G)$ and $\delta (G)$ denote the maximum and minimum degrees of vertices in $G$, respectively. In the same paper they suggested the following conjecture: every graph $G$ with $\Delta (G)-\delta (G)\le 1$ contains a maximum matching whose unsaturated vertices do not have a common neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample $G$ with $\Delta (G)=5$ and $\delta (G)=4$. In this note we show that the conjecture is false for graphs $G$ with $\Delta (G)-\delta (G)=1$ and $\Delta (G)\ge 4$, and for $r$-regular graphs when $r\ge 7$.

5 pages

Cited by in corpus (2)

• On Minimum Order of Odd Regular Graphs Without Perfect Matching
• Maximum matchings in regular graphs