Задание олимпиады о 15 государствах и дружеских соседях

На некотором острове 15 государств. У каждого из них хотя бы одно соседнее государство дружественное. Докажите, что найдётся государство, у которого чётное число дружественных соседей. (Два государства называются соседними, если у них имеетсяцелый кусок общей границы.)