Matchings and Hamiltonian Cycles in Random Graphs

摘要

This document describes matchings and Hamiltonian cycles in random graphs. It is also shown that if a random graph G with vertices (1,2,...,n) is constructed by randomly adding edges one at a time then, almost surely, as soon as G has degree k, G has (k/2) disjoint hamiltonian cycles plus a disjoint perfect matching if k is odd, where k is a fixed positive integer.