Consider a group of people in which some are friends. We assume that friendship is symmetric: if Alice is Bob’s friend, then Bob is Alice’s friend. That means we can build a friendship graph where vertices are people and edges correspond to friendships. Let’s assume that every person has at least one friend, so the friendship graph doesn’t have isolated vertices.
Darla needs to conduct research by surveying random pairs of friends. But first, she has to find those pairs. To ensure that the pairs are randomly selected, she must pick two random people from the group, contact them, and ask them whether or not they are friends. If they are, she gives them her questionnaire. If not, Darla wasted tons of time and had to keep looking.
The group she is surveying is enormous. So, when she picks two random people, they typically have never even heard of each other. Bother!
Darla decides to speed up the process. She would pick a random person, ask them for a list of friends, and then randomly pick one person from the list. Since every person has at least one friend, Darla always ends up with a filled questionnaire.
Puzzle question. Why is Darla’s method wrong? Can you describe the pairs of friends her method favors?