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 blades if there exist pairs of terminals such that each can directly communicate with the corresponding and there is a hub terminal that can directly communicate with each of the terminals . Determine the minimum value of , in terms of , such that a 3-connector with terminals always contains a windmill with blades.
Solution
The answer is
We will use connected as a synonym for directly communicating, call a set of terminals for which each of the pairs of terminals is connected complete and call a set of terminals forming disjoint connected pairs a k-matching.
We first show that for . The -terminal network consisting of two disconnected complete sets of terminals clearly does not contain an -bladed windmill (henceforth called an -mill), since such a windmill requires a set of connected terminals. So we need only demonstrate that is sufficient.
Note that we can inductively create a -matching in any subnetwork of elements, as there is a connected pair in any set of three or more terminals. Also, the set of terminals that are not connected to a given terminal must be complete, as otherwise there would be a set of three mutually disconnected terminals. We now proceed by contradiction and assume that there is a -terminal network without an -mill. Any terminal must then be connected to at least terminals, for otherwise there would be a complete set of size at least , which includes an -mill. In addition, cannot be directly connected to more than terminals, for otherwise we could construct an -matching among these, and therefore an -mill. Therefore every terminal is connected to precisely others.
If we take two terminals and that are not connected we can then note that at least one must be connected to the remaining terminals, and therefore there must be exactly one, , to which both are connected. The rest of the network now consists of two complete sets of terminals and of size , where every terminal in is connected to and not connected to , and every terminal in is not connected to and connected to . If were connected to any terminal in or , it would form a blade with this element and hub or respectively, and we could fill out the rest of an -mill with terminals in or respectively. Hence is only connected to two terminals, and therefore .

Examining the preceding proof, we can find the only 5-terminal network with no 1-mill: With terminals labeled A, B, C, D, and E, the connected pairs are (A, B), (B, C), (C, D), (D, E), and (E, A). (As indicated in the figure above, a pair of terminals are connected if and only if the edge connecting them are darkened.) To show that any 6-terminal network has a 1-mill, we note that any complete set of three terminals is a 1-mill. We again work by contradiction. Any terminal a would have to be connected to at least three others, b, c, and d, or the terminals not connected to a would form a 1-mill. But then one of the pairs (b, c), (c, d), and (b, d) must be connected, and this creates a 1-mill with that pair and a.