Problem

Source: USA TST 2006, Problem 1

Tags: graph theory, combinatorics unsolved, combinatorics



A communications network consisting of some terminals is called a $3$-connector if among any three terminals, some two of them can directly communicate with each other. A communications network contains a windmill with $n$ blades if there exist $n$ pairs of terminals $\{x_{1},y_{1}\},\{x_{2},y_{2}\},\ldots,\{x_{n},y_{n}\}$ such that each $x_{i}$ can directly communicate with the corresponding $y_{i}$ and there is a hub terminal that can directly communicate with each of the $2n$ terminals $x_{1}, y_{1},\ldots,x_{n}, y_{n}$ . Determine the minimum value of $f (n)$, in terms of $n$, such that a $3$ -connector with $f (n)$ terminals always contains a windmill with $n$ blades.