In a connected simple graph G the 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. Metivier et al. (2000) asked whether it is true that 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 the same number of nodes. In this paper we show that this is the case.
展开▼
