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

Let α(G) denote the maximum size of an independent set of vertices and μ(G) be the cardinality of a maximum matching in a graph G. A matching saturating all the vertices is a perfect matching. If α(G) + μ(G) = |V(G) | , then 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·n) time for a graph with n vertices and 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) 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 may have at most one perfect matching, and this is the case where G is a König–Egerváry graph.