Computing Unique Maximum Matchings in O(m) time for Konig-Egervary   Graphs and Unicyclic Graphs
  Let alpha(G) denote the maximum size of an independent set of vertices and mu(G) be the cardinality of a maximum matching in a graph G. A matching saturating all the vertices is perfect. If alpha(G) + mu(G) equals the number of vertices of G, then it is called a Konig-Egervary graph. A graph is unicyclic if it has a unique cycle.   In 2010, Bartha conjectured that a unique perfect matching, if it exists, can be found in O(m) time, where m is the number of edges.   In this paper we validate this conjecture for Konig-Egervary graphs and unicylic graphs. We propose a variation of Karp-Sipser leaf-removal algorithm (Karp and Spiser, 1981), which ends with an empty graph if and only if the original graph is a Konig-Egervary 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 Konig-Egervary graph. 
Vadim E. Levit and Eugen Mandrescu
cs.DM math.CO