Maximum number of different road lengths between 1000 cities Problem: 1000﻿ cities are connected by roads, and between any two cities there is a road. Also, for any two cities ﻿$A$﻿ and $﻿B﻿$, on any path from ﻿$A$﻿ to ﻿$B$﻿ passing through other cities, there is a road that is equal or shorter in length than the road from $﻿A$﻿ to $﻿B$﻿. What is the largest number of roads that can have pairwise different lengths?
My attempt at solution: Let's choose any two cities $A$ and $B$. Then let's take any other city $C$ and look at the path $A\to C\to B$. The second sentence of a problem specifies that at least one of the roads $AC$ and $CB$ is equal in length or shorter than the direct road $AB$. By swapping letters $A, B, C$ we get that any three cities form an isosceles triangle, in which legs are shorter or equal in length to the base (1).
The first sentence of a problem suggests that cities and roads between them form a complete (weighted) graph $K_n,$ where $n=1000$, and the question essentially asks what is the maximum number of different road lengths (or edge weights) can exist under these constraints.
By considering complete graphs $K_n$ with small $n$ ($n=3,4,5$) we may see that the maximum number of different edge weights (let's denote it by $L$) is $L=n-1$. Let's then make a hypothesis:
Hypothesis: For any $n\in\mathbb{N}, n>2$ we may choose weights for a complete graph $K_n$ that meets our conditions in a way that the maximum number of different edge weights is $L=n-1$.
Proof: Let's pick an edge that will have a minimal length and name corresponding vertices $A$ and $B$. Since it has to satisfy condition (1), there must be at least $n-2$ edges of minimal length connected to vertices $A$ and $B$ (because there are $n-2$ vertices left). That means that there are $n-1$ edges of minimal length in total. Let's say, for simplicity's sake, that all of these edges are connected to vertex $A$, and the only edge of minimal length connected to $B$ is coming from $A$. (Otherwise, if there exists an edge $BC$ of minimal length  between $B$ and $C$, in order to satisfy condition (1) there has to be at least one more edge of minimal length in triangle $BCD$ for any other vertex D.) It means that there is at least one unique length of edges. Let's then remove vertex A and all its edges form the initial graph. Now we get a complete graph $K_{n-1}$ that still meets our condition (1). By repeating all of the previous steps until no edges remain, increasing the minimal length on each iteration, we create a graph that satisfies all our requirements and has $L=n-1$ different edge lengths.
OK, that means that for my initial problem the answer is at least $1000-1=999$, however, now I am running into a problem. I cannot prove that this is, indeed, a maximum possible number of road lengths, nor can I think of the way to increase this number. However, I have a feeling that $n-1$ is actually the answer to the problem, since, again, by brute forcing small numbers of $n$ you come to the answer $n-1$.
I would really appreciate some help in proving or disproving this statement. Thanks!
 A: Approximately the same idea can be used for such proof.
Let $m$ be a minimal length, and let $A$ be a vertex incident to maximum number of edges with length $m$.
If there are $n - 1$ such edges, problem solved: remove $A$, remaining graph has at most $n - 2$ different lengths, adding $m$ we get at most $n - 1$ different lengths.
Otherwise, let $X$ be set of vertices connected to $A$ by edge of length $m$, and $Y$ vertices not in $X$ different from $A$.
Note that if $B \in X$, $C \in Y$, then $|BC| = m$, as either $|AC| \leq m$ or $|CB| \leq m$, and by definition of $C$, $|AC| > m$. So, any vertex from $X$ is connected to any vertex from $Y$ with edge of length $m$.
Now, split the graph into 2 parts: $X$ and $Y \cup \{A\}$. Both parts are smaller, so by induction on graph size we can assume that the former has at most $|X| - 1$ and the later at most $|Y|$ different lengths, and as parts are connected by edges of the same length ($m$), we can conclude that original graph had at most $|X| - 1 + |Y| + 1 = n - 1$ different lengths.
