The answer is $\boxed{\binom{N}{3}}.$ We can achieve this as follows. Label the oligarchs $1, 2, \cdots, N$ arbitrarily. For $1 \le i \le N,$ let the $i$th oligarch build roads between the cities owned by oligarchs $j$ and $k$ for all $1 <= j < k < i.$ Then, for any set $S$ of less than $N$ oligarchs, it's clearly impossible to reach the city of the oligarch in $S$ with the largest label from any city of the other oligarchs in $S$. Now, let's show that $\binom{N}{3}$ is actually optimal. For $N \le 3$ this can be easily verified. Suppose now that $N \ge 4$. Notice that no oligarch can build a road adjacent to their city, as then the set of $2$ oligarchs consisting of the endpoints of that road would violate the desired condition. Now, let's get an upper bound on the number of ordered triples $(a, b, c)$ such that the oligarch $a$ builds a road connecting the cities of oligarchs $b$ and $c.$ Call such triples good. Observe that this quantity is precisely twice the number of constructed roads, or $2d$ (since if $(a, b, c)$ is counted so is $(a, c, b)$). Note that from our latest result, $a, b, c$ must be distinct in any such triple. Now, notice that if $(a, b ,c)$ and $(b, a, c)$ are both good, the set of two oligarchs $\{a, b\}$ violates the condition. This then yields that for each unordered triple $(x, y, z)$ of distinct oligarchs, at most two out of the six permutations are good. Finally, we obtain that there are at most $2 \binom{N}{3}$ good triples and so we're done, as this quantity is also exactly $2d.$ $\square$

As above, the answer is $\tbinom{N}{3}$. To achieve this, the $i^{\mathrm{th}}$ oligarch builds a road between each $j,k$ with $j<i,k<i$. By hockey stick $d=\sum_{i=2}^N\tbinom{i}{2}=\tbinom{N}{3}$. We now proceed by induction on $N$, the case $N=3$ being obvious. Assuming $N\ge 4$, notice that removing all of the edges the $N^{\mathrm{th}}$ oligarch builds maintains the property that no subset of the remaining oligarchs can connect their vertices with only their edges. Thus there are at most $\tbinom{N-1}{3}$ edges remaining here, and it suffices to show that the $N^{\mathrm{th}}$ oligarch builds at most $\tbinom{N-1}{2}$ edges. But this is obvious, as otherwise the $N^{\mathrm{th}}$ oligarch must build an edge from her own vertex to some other vertex, and this pair of vertices results in a contradictory subset.

Probably the same as above , but here's the solution: The answer is $\binom{N}{3}$ . The example follows by letting the $i$-th oligarch's edges be a $K_{i-1}$ between the vertices $1,..,i-1$ Now let $E_i(j)$ be the set of edges of color $j$ passing through $i$. clearly $|E_i(i)|=0$ and $|E_i(j) \cap E_j(i)|=0$ for each $i,j$. Now consider three vertices $i,j,k$ and $E_i(j) ,E_j(k) ,E_k(i)$ . Any other vertex in our graph , has appear in at most two of these three sets. And $i,j,k$ themselves appears in at most one of these sets. But we cannot have : $ i \in E_j(k) , j \in E_k(i) , k \in E_i(j)$ at the same time. So: $$|E_i(j)| + |E_j(k)| + |E_k(i)| \le 2(N-2)$$Now adding this up on every three vertices in the graph , we count every edge at least $2(N-2)$ ; that's because an edge $e$ between $i,l$ had come twice in $E_i(j)$ and $E_l(j)$ for a fix $j$ and we have $N-2$ other choices for $k$. So the total number of edges is at most: $\frac{\binom{N}{3}.2(N-2)}{2(N-2)} = \binom{N}{3}$ And we're done.