First replace 2024 with $N$ a positive integer ,now call a set $A$ of cities cool if it is possible to go from one city to another one in $A$. Claim : For any $N >6$ there exist a cool set $A$ with atleast $N-2$ elements. Proof; we will apply induction on $N$ ,suppose for some $K$ >6 there exist a cool set with atleast $K-2$ elements. .For $K+1$ ,consider cool set $A$ and there will be 3 cities ( say $ P,Q,R $) not belonging to $A$ (otherwise we are done! ) now clearly by above condition atleast one of cities $ P,Q ,R$ will belong to $A$ so we have |$A$|> $K-2$ and completing the induction hypothesis. It suffices to show that $N$ =7 holds . Claim ; there will atleast 3 routes between any 6 cities. Proof; simple so we get 2 possible cases . Case1; In given 6 cities there will be 3 pairs (A,B) ,(C,D) and (E,F) of connected cities so let $G$ be remaining one. and notice that $G$ will connect with atleast one cities of 2 distinct pairs ! Case2; or there exist a cool set $T$ with 4 elements If |$T$|>4 we are done otherwise $G$ will connect with atleast one city of $T$ because if $T$ = $(A, B, C, D)$ , then consider 2 triples ($G, E, F$) , ($A, B, C$) , we get desired conclusion!

Let $P$ be the longest path. Set $A,B$ as the first and last vertices of $P$. Let $P=\overline{Av_1v_2...v_kB}$. First, let's show that $|P|\geq 2021$. Suppose not. Let $X,Y,Z,T$ be outer vertices. Note that there is no edge between $(A,B)$ and $(X,Y,Z,T)$. There is an edge between $(X,Y,Z)$ and $(A,B,v_i)$ thus, $v_i$ is connected to at least one of $(X,Y,Z)$. WLOG $X$ and $v_2$ are connected. There is an edge between $(Y,Z,T)$ and $(A,B,X)$. Suppose that $X$ and $T$ are connected. The path $\overline{TXv_2...v_kB}$ is longer than $P$ which is a contradiction. Hence $|P|\geq 2021$. Suppose that $|P|=2021$. Let $X,Y,Z$ be the vertices not in $P$. If $X$ is connected to both $v_i$ and $v_{i+1}$, then $\overline{Av_1...v_iXv_{i+1}...v_{2019}B}$ is longer than $P$ which is impossible so none of $(X,Y,Z)$ is connected to consecutive vertices on $P$. Assume that both $v_{i-1}$ and $v_{i+1}$ are connected to $X$. If $v_i$ and $A$ are neighbours, then $\overline{v_{i-2}...Av_iv_{i-1}Xv_{i+1}...B}$ is longer than $P$, if $v_i$ and $B$ are neighbours, then $\overline{A...v_{i-1}Xv_{i+1}v_iBv_{2019}...v_{i+2}}$ is longer than $P$. Thus, none of $(X,Y,Z)$ is connected to both $v_{i-1}$ and $v_{i+1}$. We observe that if $v_1,v_2$ are connected to $X,Y$ respectively, then $v_{1(mod \ 3)},v_{2(mod \ 3)},v_{0(mod \ 3)}$ are connected to $X,Y,Z$ respectively. However, $\overline{Av_1Xv_4v_3v_2Yv_5...v_{2019}B}$ is longer than $P$ which result in a contradiction as desired.$\blacksquare$