Q8 Matemática  (IMO Shortlist 1986)

De uma coleção de $n$ pessoas $q$ equipes distintas de dois membros são selecionadas e classificadas $1,\cdots ,q$ (sem empates). Seja $m$ o menor inteiro maior ou igual a $2q/n$. Mostre que existem $m$ equipes distintas que podem ser listadas de modo que: (i) cada par de equipes consecutivas na lista tenha um membro em comum e (ii) a cadeia de equipes na lista esteja em ordem de classificação. Formulação alternativa. Dado um grafo com $n$ vértices e $q$ arestas numeradas $1,\cdots ,q$, mostre que existe uma cadeia de $m$ arestas, $m\ge \frac{2q}{n}$ , cada duas arestas consecutivas com um vértice comum, dispostas monotonicamente em relação à numeração.