Solution:

Call a metro line charming if it contains exactly one of the stations David wants to visit, and breathtaking if it contains two such stations. Every train station in $S$ has $k$ metro lines passing through it, of which $k-1$ link it to other members of $S$ and are breathtaking, and the last one is charming. In particular, we have a one-to-one correspondence between charming metro lines and stations in $S$ and so there are $k$ charming metro lines.

Consider now an arbitrary breathtaking metro line $M$ and an arbitrary station $s$ on that line. We claim $s$ must lie on exactly one charming metro line. Note that this has already been proven for stations in $S$, so suppose $s \notin S$. Firstly, it has to lie on a charming metro line, because every breathtaking metro line connects it to two stations in $S$ but this is a disjoint partition of $S$ and $S$ has an odd number of elements. However, there must now be at least one charming metro line for every element of $M$ and these metro lines must be distinct, meaning there is necessarily a one-to-one correspondence and there is exactly one charming metro line passing through every station on $M$.

Consider now the intersection of two charming lines. This station cannot lie on a breathtaking line by the converse of the previous claim. It follows that it must lie on all the charming lines, in order for it to be possible to go from it to stations in $S$ without changing metro line. This intersection is therefore the desired station.

Solution:

As before, consider charming and breathtaking metro lines, and call a metro line dull if it contains no elements of $S$. It is easy to see there is at least one dull metro line, as it is not difficult to compute that we have $k$ charming metro lines, $\frac{k(k-1)}{2}$ breathtaking metro lines but $k^{2}-k+1$ metro lines in total (the last computation follows from the fact that there are as many metro lines as stations by double counting, and you can count the number of stations as $k(k-1)+1$ by considering an arbitrary station and looking at the distinct stations on each metro line it is on). Furthermore, these three definitions give a trichotomy on the metro lines.

Consider an arbitrary dull metro line $D$. Every station on $D$ needs to lie on at least $\frac{k+1}{2}$ non-dull metro lines, to connect it to the $k$ (odd) stations in $S$, since each non-dull metro line can connect it to at most 2 of these. Additionally, there is a bijection between non-dull metro lines and stations in $D$ by the unique intersection of metro lines condition. As there are $\frac{k(k+1)}{2}$ non-dull metro lines in total, every station on a dull metro line must lie on exactly $\frac{k^{2}+1}{2}$ non-dull metro lines, of which exactly one is charming.

Now consider the intersection of two charming metro lines. If this station lies on a dull metro line, this contradicts what we have just proven. So it cannot lie on a dull metro line and since it lies on $k$ metro lines each of which connect it to at least one station in $S$, every metro line it is on must connect it to a different station in $S$.

Solution:

As before, consider charming and breathtaking metro lines. In particular, it is not too hard to show every station not in $S$ is on at least one charming line, by a simple parity argument.

Now, we place an upper bound on the number of stations not in $S$. As shown in previous solutions, we know there are $k$ charming lines, so order this arbitrarily. The first charming line contains exactly $k-1$ stations not in $S$. The second charming line contains at most $k-2$ new stations not in $S$, as it must intersect with the previous charming line in at least one station. The third charming line contains at most $k-2$ new stations, as it must intersect with the previous charming lines in at least one station. Continuing in this manner, we obtain a total upper bound of $k-1+(k-2)(k-1)=k^{2}-2 k+1$ stations not in $S$.

However, as in previous solutions, one can show there are $k^{2}-k+1$ stations in total, meaning this bound is tight and during our bounding process, each charming metro line had to provide $k-2$ new stations. This implies that all the charming metro lines intersect in one station, which is the desired station.