MathDB

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.

Problem Statement