Problem 6

In the plane, let a set of

n

points,

n\\ge3

, be given, and join every pair by a segment. Let

d

be the length of the longest segment. A diameter is any joining segment of length

d

. Prove that the number of diameters is at most

n

Step 2 of 4: Use the counting contradiction

Previous step Next step

E>n\\Longrightarrow\frac{2E}{n}>2\\Longrightarrow\text{some vertex is incident with at least three diameters}.

Detailed analysis

Assume there are $E>n$ diameters and view them as edges of a graph on the given points. The average diameter-degree is $2E/n>2$ , so some point $A$ is incident with at least three diameters $AB,AC,AD$ . Choose the ray $AC$ between $AB$ and $AD$ .