The probability of a rendezvous is minimal in complete graphs

following random experiment is carried out: each node chooses one
of its neighbors uniformly at random. We say a rendezvous occurs
if there are adjacent nodes u and v such that u chooses v
and v chooses u . It was posed as an open problem by
Metivier et al. if the probability for a rendezvous
to occur in G is at least as large as the probability of a rendezvous
if the same experiment is carried out in the complete graph on n
nodes. We discuss the problem and prove the statement. -