From a collection of
persons
distinct two-member teams are selected and ranked
(no ties). Let
be the least integer larger than or equal to
. Show that there are
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
vertices and
edges numbered
, show that there exists a chain of
edges,
, each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![q](/media/m/c/1/d/c1db9b1124cc69b01f9a33595637de69.png)
![1, \cdots, q](/media/m/3/4/1/3419347dee81dc2d5d8aed2f695ad869.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![2q/n](/media/m/8/c/a/8ca8a2df04352aba3f5e7c088b95923a.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
(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](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![q](/media/m/c/1/d/c1db9b1124cc69b01f9a33595637de69.png)
![1, \cdots , q](/media/m/b/6/2/b62a1a1483c72856a4cec5f1a366df83.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![m \geq \frac{2q}{n}](/media/m/6/2/9/629db9208fe5c8e7f86eca273f6debf8.png)