Computing unique maximum matchings in $$O(m)$$ O ( m ) time for König–Egerváry graphs and unicyclic graphs

Let $$\alpha \left( G\right) $$ α G denote the maximum size of an independent set of vertices and $$\mu \left( G\right) $$ μ G be the cardinality of a maximum matching in a graph $$G$$ G . A matching saturating all the vertices is a perfect matching. If $$\alpha \left( G\right) +\mu \left( G\right) =\left| V(G)\right| $$ α G + μ G = V ( G ) , then $$G$$ G is called a König–Egerváry graph. A graph is unicyclic if it is connected and has a unique cycle. It is known that a maximum matching can be found in $$O(m\cdot \sqrt{n})$$ O ( m · n ) time for a graph with $$n$$ n vertices and $$m$$ m edges. Bartha (Proceedings of the 8th joint conference on mathematics and computer science, Komárno, Slovakia, 2010) conjectured that a unique perfect matching, if it exists, can be found in $$O(m)$$ O ( m ) time. In this paper we validate this conjecture for König–Egerváry graphs and unicylic graphs. We propose a variation of Karp–Sipser leaf-removal algorithm (Karp and Sipser in Proceedings of the 22nd annual IEEE symposium on foundations of computer science, 364–375, 1981) , which ends with an empty graph if and only if the original graph is a König–Egerváry graph with a unique perfect matching (obtained as an output as well). We also show that a unicyclic non-bipartite graph $$G$$ G may have at most one perfect matching, and this is the case where $$G$$ G is a König–Egerváry graph.