Example 3 In a country, there are $n$ cities and $n$ nobles, each noble owning one city. Now, each noble has built roads between some cities, and a noble can build at most one road between any two cities (note that there can be multiple roads between two cities, but they belong to different nobles). Suppose all nobles have built a total of $d$ roads. Now, some nobles want to form a "group" such that the cities within the group are connected by roads within the group (it is allowed to pass through cities outside the group as long as the roads belong to the group). However, the nobles find that no group of more than one and fewer than $n$ nobles can form a group. Find the maximum value of $d$ under this condition. ${ }^{[3]}$
(2020, St. Petersburg Mathematical Olympiad)
【Analysis】Label the cities as $1,2, \cdots, n$. For any three numbers $a<b<c$, connect a road of color $a$ between $b$ and $c$. This construction satisfies the requirements, and at this point, there are $\mathrm{C}_{n}^{3}$ roads in total.
We now prove the maximality of $\mathrm{C}_{n}^{3}$.
We use induction on $n$.
When $n=3$, it is easy to see that the maximum value is $\mathrm{C}_{n}^{3}$.
Assume that for $n=k(k \geqslant 3)$, the conclusion holds.
Then for $n=k+1$, two cities cannot be connected by roads of these two colors, otherwise, these two cities do not meet the requirements.

For three different cities $a, b, c$, if city $a$ and $b$ are connected by a road of color $c$, then $a$ and $c$ cannot be connected by a road of color $b$, and $b$ and $c$ cannot be connected by a road of color $a$, otherwise, the three cities $a, b, c$ do not meet the requirements.

Now consider the roads of color $a$ and the roads connected from city $a$. A bijection can be established between them and pairs of the remaining $k$ cities $(b, c)$.

Thus, the sum of the number of roads of color $a$ and the roads connected from city $a$ is no more than $\mathrm{C}_{k}^{2}$.

By the induction hypothesis, after adding city $a$, the maximum number of roads that can be built is $\mathrm{C}_{k}^{3}+\mathrm{C}_{k}^{2}=\mathrm{C}_{k+1}^{3}$.
By mathematical induction, we know that the maximum value of $d$ is $\mathrm{C}_{n}^{3}$.