4. Answer: $n^{2}-n+1$.

First, for $k \leqslant n^{2}-n$, there exists a cable car route such that no two stations are connected by both companies.

It is clear that we only need to provide an example for $k=n^{2}-n$, and for smaller $k$, we can simply remove some cable cars.

Let $S_{1}, S_{2}, \cdots, S_{n^{2}}$ be $n^{2}$ stations with heights in increasing order. Consider company $A$'s $n^{2}-n$ cable cars, running from $S_{i}$ to $S_{i+1}\left(1 \leqslant i \leqslant n^{2}\right)$, and $n+i$; company $B$'s $n^{2}-n$ cable cars, running from $S_{i}$ to $S_{i+n}\left(1 \leqslant i \leqslant n^{2}-n\right)$. Thus, $S_{i}$ and $S_{j}$ are connected by company $A$ if and only if $\left\lceil\frac{i}{n}\right\rceil=\left\lceil\frac{j}{n}\right\rceil$, and by company $B$ if and only if $i \equiv j(\bmod n)$, where $\lceil x\rceil$ denotes the smallest integer not less than the real number $x$. Clearly, these two conditions cannot be satisfied simultaneously, so no two stations are connected by both companies $A$ and $B$.

Next, we prove that when $k=n^{2}-n+1$, there must be two stations connected by both companies.

Define a directed graph $G_{A}$, with the vertex set being the $n^{2}$ stations $\left\{S_{1}, S_{2}, \cdots, S_{n^{2}}\right\}$. For $1 \leqslant i<j \leqslant n^{2}$, there is a directed edge $S_{i} \rightarrow S_{j}$ if and only if company $A$ has a cable car running from $S_{i}$ to $S_{j}$.

By the condition, each vertex in $G_{A}$ has at most one outgoing edge and at most one incoming edge, and since the directed edges can only point from a vertex with a smaller index to a vertex with a larger index, $G_{A}$ does not contain any directed cycles.

It is easy to see that $G_{A}$ is the union of several directed chains (an isolated vertex is also considered a directed chain). Each pair of stations on a directed chain is connected by company $A$. Since there are $n^{2}-n+1$ edges, $n^{2}-n+1$ vertices have incoming edges, and exactly $n-1$ vertices have no incoming edges, $G_{A}$ has $n-1$ directed chains. By the pigeonhole principle, one of these directed chains must contain at least $\left[\frac{n^{2}}{n-1}\right]=n+2$ vertices. Let the set of vertices on this directed chain be $X$, with $|X| \geqslant n+2$.

Similarly, define the directed graph $G_{B}$, and we find that $G_{B}$ also has $n-1$ directed chains. Therefore, there are two vertices $S_{i}$ and $S_{j}$ in $X$ that are on the same directed chain in $G_{B}$. Thus, $S_{i}$ and $S_{j}$ are connected by both companies $A$ and $B$.
4. Given an integer $n>1$. On a mountain, there are $n^{2}$ cable car stations of different heights. There are two cable car companies $A$ and $B$, each operating $k$ cable cars; each car runs from one station to a higher station (without stopping at any other stations). Company $A$'s $k$ cable cars have $k$ different starting points and $k$ different endpoints, and the cable car with a higher starting point also has a higher endpoint. Company $B$'s cable cars also meet the same conditions. We say that two stations are "connected" by a company if and only if it is possible to travel from the lower station to the higher station using one or more cable cars of that company (no movement between stations is allowed). Find the smallest positive integer $k$, such that there are definitely two stations connected by both companies.