This problem is proposed by Ilya Bogdanov and the answer is $200$

Indeed, the answer is $d=200$. The construction is simply a $201$-cycle: any two adjacent vertices has a shortest even path between them of length $200$. Otherwise, given such a graph $G$, consider the shortest even path $p$ between vertices $A$ and $B$, and suppose it is of length $>200$. Also, let the vertex in the middle of the path be $C$. Now there are two sections of the path: $p_{AC}$ and $p_{CB}$, each of length $>100$. Consider the shortest path between $A$ and $C$ (denoted $q_{AC}$). If $q_{AC} \equiv p_{AC}\pmod 2$, then we may replace $p_{AC}$ with $q_{AC}$ to get a shorter path. Otherwise, $q_{AC}\not\equiv p_{AC}\pmod 2$, and similarly $q_{CB}\not\equiv p_{CB}\pmod 2$, then we replace $p$ with $q_{AC}$ and $q_{CB}$. This improvement is always possible if the length of $p$ is more than 200.

We claim that the answer is $200$. The construction is to just take a $C_{201}$. We now prove the bound Take the natural graph interpretation. Consider a edge $xy$ and two points $A,B$ in the graph such that all the four vertices lie in the same connected component. Denote the distance of any point $v$ from $B$ by $d_b(v)$. Note that $\vert d_b(x)-d_b(y)\vert \le 1$. We claim that we must have a edge $xy$ with $d_b(x)=d_b(y)$. Assume not then we note that we can only have a edge between vertices whose $d_b(\bullet)$ value is of different parity. This means that any route between two cities in the same connected component must be of odd length (contradiction). Hence pick $xy$ with $d_b(x)=d_b(y)$. Suppose we can reach from $A$ to $X$ in $a$ flights and we can reach from $x$(or $y$) to $B$ in $b$ flights. Then we can reach from $A\mapsto B$ in $a+b$ flights or $a+b+1$ flights one of which is even and is $\ge 100+100=200$.$\blacksquare$

So long since last I've posted. Anyway here's my solution Firstly d is even, because odd value $d$ and $d-1$ will both do for the problem, but $d-1$ i smaller, contradiction. I started this problem as a game: what if d was arbitrarily large, then cut a lot, and for some reason I always found that the graphs of such d have something in common. Let $d \ge 202$, that means there is a shortest even path from two cities, call them $A$ to $B$ with length $d \ge 202$. Let the sequence of cities in this path be $S={x_{1}, ..., x_{d-1}, B}$. This applies for the path from $B$ to $A$ also, which is just the said sequence in reverse. Observe $x_{101}$ and $x_{d-101}$. The sub-sequence from $A$ to $x_{101}$ is of length $101>100$ (and odd!), so there must be another path from $A$ to $x_{101}$ of length $k \le 100$. Now, if $k$ is odd, then we'd have a closer even path from $A$ to $B$ through this other path, so $k$ is even. Similarly, there is an even path of length $l \le 100$ from $B$ to $x_{d-101}$, and vice versa. This is fishy because now the path from $A$ to $x_{101}$ with length $k$, then the sub-sequence of $S$ that is $x_{101}$ to $x_{d-101}$ (which is $d-202$ long, and even), and the path from $x_{d-101}$ to $B$ with length $l$ altogether is an even path from $A$ to $B$ with length at most $d-202 + 100 + 100 = d-2$, Contradiction! So $d \le 200$. Which would be easy to see correct from a cycle of $201$.