Random near-regular graphs and the node packing problem (Q1065829)

The graph G is bicritical if its vertex-set contains at least two elements and after deleting any vertex (and its incident edges) from the original G the remainder has a 2-matching. It is proved that the probability that \(G_ n(m)\) is bicritical tends to either 0 or 1 as n increases to infinity if either \(m=1\) or \(m\geq 3\), respectively, and the limit of the upper bound of this probability is less than 1 in the case \(m=2\). \(G_ n(m)\) is defined here as a graph with n, \(n>1\), vertices in which preliminarily the edges are chosen in m independent trials performed for each vertex in separation with the constant density \((n- 1)^{-1}\), and, finally, multiple edges are merged into single ones.