From a collection of n persons q distinct two-member teams are selected and ranked 1,⋯,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,⋯,q, show that there exists a chain of m edges, m≥n2q , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering. combinatoricsgraph theorypermutationExtremal Graph TheoryIMO Shortlist