證明：假設(shè)每兩人的公共朋友數(shù)均為奇數(shù)，則任一人的朋友數(shù)為偶數(shù)．
理由如下：
任取一人A，有朋友F₁，F(xiàn)₂，…，F(xiàn)_k，
用（AF_i）表示A與F_i的公共朋友數(shù)，（AF_i）為奇數(shù)．
∵每兩個F_i之間增加一對朋友關(guān)系，AF_i之和加2．
（比如，F(xiàn)₁與F₂是朋友，則AF₁中會計算一次F₂，AF₂中會計算一次F₁），
故

k

i＝1

AFi一定是偶數(shù)，
則k一定是偶數(shù)．
同理F_i朋友數(shù)一定也是偶數(shù)，且包括A．
由于k是偶數(shù)，
∴F_i朋友數(shù)之和也是偶數(shù)．
A在F_i朋友數(shù)之和中出現(xiàn)了k次，
剩余2n-1人如在F_i朋友數(shù)之和均出現(xiàn)奇數(shù)次的話，
F_i朋友數(shù)之和應(yīng)是奇數(shù)，
所以剩余2n-1人中至少有一人B在F_i朋友數(shù)之和中出現(xiàn)偶數(shù)次，
這意味著A與B在F_i朋友中共同好友為偶數(shù)個，
即AB為偶數(shù)．