# zbMATH — the first resource for mathematics

On matchings and Hamiltonian cycles in random graphs. (English) Zbl 0592.05052
Random graphs ’83, Lect. 1st Semin., Poznań/Pol. 1983, Ann. Discrete Math. 28, 23-46 (1985).
[For the entire collection see Zbl 0582.00006.]
A graph is chosen randomly from the set of graphs of order n and size $$m=m(n)$$ having no isolated vertices. The limiting probability of a graph with a perfect matching is obtained. It is also shown that if a graph of order n is constructed by randomly adding edges one at a time then, almost surely, as soon as the minimum degree is equal to any fixed positive integer k, there are $$\lfloor k/2\rfloor$$ disjoint hamiltonian cycles and, if k is odd, a disjoint perfect matching.
Reviewer: O.Frank

##### MSC:
 05C80 Random graphs (graph-theoretic aspects) 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs
##### Keywords:
random graphs; hamiltonian cycles; perfect matching