Question 8
(USA 1) From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1,\ldots,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,\ldots,q$, show that there exists a chain of $m$ edges, $m\ge2q/n$, each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
Alternative formulation. Given a graph with $n$ vertices and $q$ edges numbered $1,\ldots,q$, show that there exists a chain of $m$ edges, $m\ge2q/n$, each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.