A simple a. s. correct algorithm for deciding if a graph has a perfect matching (Q1902903)

A fast algorithm for deciding whether a graph of even order has a perfect matching is given. The algorithm is based on the following result. Let \(G\) be a graph of even order and let \(S\subset V(G)\). If \(G\backslash S\) has more than \(|S|\) odd connected components, we call \(S\) a forbidden structure of type \((|S|; \gamma_1, \gamma_2,\dots, \gamma_{|S|+ 1})\), where \(\gamma_1, \gamma_2,\dots, \gamma_{|S|+ 1}\) are the cardinalities, in increasing order, of the smallest \(|S|+ 1\) odd components in \(G\backslash S\). Let \(G\) be randomly chosen according to the uniform distribution on the set of all graphs on \(n= 2k\) vertices. Let \(q_1= \text{Pr}\) \{\(G\) has forbidden structure of type \((1; 1, 1)\)\}, and \(q_2= \text{Pr}\) \{\(G\) has forbidden structure of type different from \((0; 1)\) and \((1; 1, 1)\)\}. Then \(q_2= O(q_1)\).