The country has 300 cities, some pairs of cities are connected by roads. It turned out that for any four cities from any city of this four you can get to any other city of this four without passing through the remaining 296 cities. At what is the largest n in the country, it is possible to choose n cities so that any two selected cities are connected by road?
This is definitely a graph problem. I've solved problems like this with anti-edges (like if two vertices are not connected then they are connected with anti-edges) But now it doesn't help
Let $G$ be a graph whose vertices are the cities and the vertices are adjacent iff they are not connected by a road. Then the question is about the size of a largest independent set of vertices of $G$.
If $G$ has a vertex $v$ of degree at least three then $v$ together with its three neighbors constitute a set of four cities violating the question condition. Thus each vertex of $G$ has degree at most two. It easily follows that $G$ is a union of vertex-disjoint cycles or paths. Moreover, the question condition implies that $G$ has no cycles of length four.
Conversely, if $H$ is any graph which is a union of vertex-disjoint cycles (of length distinct from four) or paths then in the complement of $H$ any induced four-vertex subgraph $F$ is connected. Indeed, if the vertices of $F$ do not belong to one connected component of $H$, then $F$ contains a copy of a complete $k$-partite subgraph for $k\ge 2$ (that is, $K_{1,3}$, $K_{2,2}$, $K_{2,1,1}$ or $K_{1,1,1,1}$), so it is connected. If the vertices of $F$ belong to one connected component of $H$ then it easy to see that $F$ contains a copy of a path with four vertices, so it is connected.
Since a cycle (path) with $k$ vertices contains an independent set of size $\lfloor k/2\rfloor$ ($\lceil k/2\rceil$), which is at least $k/3$, $G$ has an independent set of size at least $300/3=100$ and this minimum is attained when $G$ is a union of vertex-disjoint triangles.