Sorry for reviving but any solution for this?

Plug $n$ instead $2016$. Then the answer is $k=\lceil 3n/2\rceil-1$. That's the threshold. In order to prove that, we should take care of two things. 1) To construct a graph with $n$ vertices and $\lceil 3n/2\rceil$ edges, such that removing any independent set of vertices still leaves the graph connected. 2) For any graph with less than $\lceil 3n/2\rceil$ vertices, it's possible to remove some independent set of vertices, such that the remaining graph is disconnected. The proof of both 1) and 2) goes by induction with separate cases for different parity of $n$. 1) For $n=6$, consider two triangles $A_1A_2A_3, B_1B_2B_3 $ with $A_iB_i, i=1,2,3$ connected. The transition $n\to n+1$, where $n$ is even is as follows. Let $G_n$ is a corresponding graph for $n$. (it's 3-regular as the following induction step will show). Consider an edge $ab$ of $G_n$ and $x$ be an additional vertex not in $G_n$. We add to $G_n$ the edges $xa$ and $xb$. It's the graph $G_{n+1}$. Check that it has the required property. The transition $n\to n+2$ ($n$-even). Take an triangle $abc$ in $G_n$ and additional vertices $x,y$ Add the edges $xy, xa,xb, ya,yc$ and remove $ab, ac$. The new graph $G_{n+2}$ has the needed property. Also, $G_{n+2}$ is $3$-regular(all degrees equal to 3), providing $G_n$ is 3-regular (like G_6). 2) Also induction. Suppose it's proven for all $n<m$. We want to establish it for $n=m$. Again two cases depending on parity of $m$. a) $m$-even, the edges of $G_m$ are less than $3m/2$. Then there are at least 2 vertices $x,y$ with degrees at most $2$. If $x,y$ are not connected we remove both $x,y$. If they are connected- only one of them. Consider the remaining graph $G'$. There is some case chasing but the idea is to apply the induction hypothesis to $G'$ and see that we can break $G$ too. b) $m$=odd, $G_m$ is with at most $\lfloor 3m/2 \rfloor$. There exists at least one vertex $x$ with degree $2$. Fortunately (because $m$ is odd), removing it, we also can apply the induction hypothesis to the remaining graph $G'$, that's we can break $G'$ by removing some independent set $S$ of vertices. Then removing $S\cup \{x\}$ will leave $G_m$ also disconnected. Comment. It's all about the information $k=\lceil 3n/2\rceil-1$. When one gets that it's the threshold, the rest is not so difficult. There easily comes an example of graph of $n$ vertices and $2n-1$ edges that couldn't be broken. Take 2 vertices, connect them, and connect each of them with the rest $n-2$ vertices. I decided $k=2n-2$ and it took me some time to understand it's a delusion. Maybe the easiest way is to check $n=6$ and see that that there is a graph with $9$ edges that couldn't be broken, it's 3-regular and thus to suspect $k$ is something about $3n/2$.

In my humble opinion this is way too hard for a JBMO TST!

Edit:You should clarify your induction for the construction part.It is important which triangles you choose when you add 2 vertices $x$ and $y$,there is an example which doesn't work.I will try on my own to find an example which works,please post it in more detail. For $n=4$ the anwer is $[3n/2]$$-$$2$,or $4$.I am not saying the solution,I read it and I am trying to figure out why it is true.It would be great if you could post a more detailed version where you explain things.I will try to understand the solution on my own,I may ask you some questions,maybe you could be more detailed in the part of the proof where you prove it is always possible for $k<[3n/2]$ and also maybe prove why the constructed examples work.But I am more interested in the first thing I mentioned,and please say does everything stand correct beacause of the $n=4$ case.Is true for $n>5$?

The answer for $n$ cities is $k=2n-4$. Let us reformulate the problem in terms of graph theory. Suppose that for any connected graph with $k$ edges and $n$ vertices one can choose some vertices no two directly connected by edges such that after removal of all chosen vertices (and their edges) the remaining graph becomes disconnected (this removal will be called a proper removal). Find the maximal value of $k$. Let us show that $k\le 2n-4$. Consider a graph such that there are edges between $v_i$ and $v_{i+1}$ for each $i=1, 2, 3, \dots, n-1$ and $v_1$ is connected to all other vertices. It can be readily shown that this graph with $n-2+n-1=2n-3$ edges has no proper removal and therefore $k\le 2n-4$. Now we show that any connected graph with at most $2n-4$ edges has proper removal. WLOG we will assume that the graph is $2$-connected, otherwise there is a vertex which removal makes the graph disconnected. We will use the induction over $n$ and for being able to carry out the inductive hypothesis we will prove a stronger statement: Lemma: Let $G$ be a $2$-connected graph with at most $2n-4$ vertices ($n\ge 4$) and $v_0$ be its fixed vertex. Then there is a proper removal not including $v_0$. Proof. The induction base: The case $n=3$ is simple, since there is no $2$-connected graph with $2\cdot 3-4=2$ edges. The case $n=4$ is simple, the only $2$-connected graph is a cycle. Consider a graph with $n$ vertices. Suppose that $v_0$ is not in a triangle. Since $G$ is $2$-connected it is not a star and after removing of all neighbours of $v_0$ we will get a disconnected graph. Suppose that $v_0$ is in the triangle $v_0,v_1,v_2$. Let $G'$ be a graph obtained by merging of the vertices $v_0$ and $v_1$ into $v'$ (if $G$ contains at least one of the edges $(v_0,w)$ and $(v_1,w)$ then $G'$ contains the edge $(v',w)$. In merging process the graph $G'$ "lost" the edges $(v_0,v_2),$ $(v_1,v_2),$ $(v_0,v_1)$ and "gained" the edge $(v',v_2)$. Therefore, the total number of edges has decreased at least by $2$. Thus, $G'$ has atmost $2(n-1)-4$ edges. If $G'$ is $2$-connected then it has a proper removal not containing $v_0$ and this is also a proper removal for $G$. Let $V(G)$ be the set of all vertices of $G$ and $E(G)$ be the set of all edges of $G$. Suppose that $G'$ is not $2$-connected. Then the removal of $v_0$ and $v_1$ makes $G$ disconnected. It means that there are $2$-connected graphs $G_1,\dots, G_s$ such that each $G_i$ has at least three vertices, $V(G_i)\cap V(G_j)=\{v_0,v_1\}$ and $G=\cup_{i=1}^s G_i$. If some $G_i$ has a proper removal not containing $v_0$ then it is also a proper removal of $G$ and we are done. If no $G_i$ has a proper removal not containing $v_0$ then by inductive hypothesis each $G_i$ has at least $\vert V(G) \vert -3$ edges and $$\vert E(G) \vert=\sum_{i=1}^s \vert E(G_i) \vert -s+1 \ge \sum_{i=1}^s(2\vert V(G_i) \vert -3)-s+1$$$$=2\sum_{i=1}^s \vert V(G_i) \vert -4s+1=2n+4(s-1)-4s+1=2n-3$$which contradicts the assumption. Done. Thus, the answer is $2\cdot 2016-4=4028$.