IMO 1985 LL USA89

Given that n elements a1, a2, . . . , an are organized into n pairs

imolonglistmathematicsolympiad

IMO 1985 LL USA89

Origin: USA

Problem

Given that n elements a1, a2, . . . , an are organized into n pairs P1, P2, . . . , Pn in such a way that two pairs Pi, Pj share exactly one el- ement when (ai, aj) is one of the pairs, prove that every element is in exactly two of the pairs.