  Say that a graph G has property $\mathcal{K}$ if the size of its maximum
matching is equal to the order of a minimal vertex cover. We study the
following process. Set $N:= \binom{n}{2}$ and let $e_1, e_2, \dots e_{N}$ be a
uniformly random ordering of the edges of $K_n$, with $n$ an even integer. Let
$G_0$ be the empty graph on $n$ vertices. For $m \geq 0$, $G_{m+1}$ is obtained
from $G_m$ by adding the edge $e_{m+1}$ exactly if $G_m \cup \{ e_{m+1}\}$ has
property $\mathcal{K}$. We analyse the behaviour of this process, focusing
mainly on two questions: What can be said about the structure of $G_N$ and for
which $m$ will $G_m$ contain a perfect matching?

Combinatorics