ILL 1986 Problem 74

From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that : (i) each pair of consecutive teams on the list have one member in common and (ii) the chain of teams on the list are in rank order.

Alternative formulation. Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$, each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.