Show that there are at most $n^2$ roads. There are $2n$ places. If place $a$ and place $b$ has a road between them and place $b$ and place $c$ has a road between them, then there is no road between place $a$ and place $c$.
Now show that there are at most $n^2$ roads.
I observed that if we also include the odd number of places during examination of the total number of roads, a pattern is found. When total number of places is 0, 1, 2, 3, 4, 5, 6, 7; the maximum number of paths are 0, 0, 1, 2, 4, 6, 9, 12 respectively. The differences between the maximum number of paths are like 0, 1, 1, 2, 2, 3, 3 respectively.
Another approach can be: We can choose two places in $^nC_2$ ways and then subtract $^nC_3$ (every triangle formed). I am not sure of this. 
 A: Let us form a graph $V$ where $V= \{1,2,\ldots,2n\}$, and $i\leftrightarrow j$ if $i$-th place and $j$-th place are connected by a road between them. Each place is not connected with itself. Let $d_i$ denote the number of $j$ such that $i\leftrightarrow j$. Then we can see that the number of edges is $$N = \frac{1}{2}\sum\limits_{i\in V}d_i.$$ Our goal is to show $N\le n^2$. Let us define
$$
M=\sum_{i\leftrightarrow j}\sum_{k\in V}\left(1_{i\leftrightarrow k}+1_{j\leftrightarrow 
 k}\right)
$$ where $1_{j\leftrightarrow k}=1$ if $j\leftrightarrow k$ and is $0$ otherwise. By the assumption, there is no $k$ such that $ 1_{i\leftrightarrow k}+1_{j\leftrightarrow 
 k}=2.$ This gives
$$
M\le \sum_{i\leftrightarrow j}\sum_{k\in V}1=2n\sum_{i\in V} d_i= 4nN.
$$ On the other hand, we have
$$\begin{eqnarray}
M=\sum_{k\in V}\sum_{i\leftrightarrow j}\left(1_{i\leftrightarrow k}+1_{j\leftrightarrow 
 k}\right)&=&\sum_{k\in V}\sum_{i\leftrightarrow j}1_{i\leftrightarrow k} +\sum_{k\in V}\sum_{i\leftrightarrow j}1_{j\leftrightarrow k}\\
&=&2\sum_{k\in V}\sum_{i\leftrightarrow j}1_{i\leftrightarrow k}\\
&=&2\sum_{k\in V}\sum_{i\in V}1_{i\leftrightarrow k}\sum_{j:i\leftrightarrow j}1\\
&=&2\sum_{k\in V}\sum_{i\in V}1_{i\leftrightarrow k}\cdot d_i\\
&=&2\sum_{i\in V}d_i\sum_{k\in V}1_{i\leftrightarrow k}\\
&=&2\sum_{i\in V}d_i\cdot d_i = 2\sum_{i\in V} d_i^2.
\end{eqnarray}$$ By Cauchy-Schwarz, we have
$$
n\cdot M=|V|\cdot\sum_{i\in V} d_i^2\ge \left(\sum_{i\in V}d_i\right)^2=4N^2
$$ Since $M\le 4nN$, it follows
$$
4N^2\le 4n^2N,
$$ that is,
$$
N\le n^2
$$as desired.
A: It's equivalent to prove that in graph with $2n$ vertices without triangles there at most $n^2$ edges. However, it's a case of Turán's theorem (about $K_{r}$-free graphs) for $r=3$. You can find several proofs of this theorem in Proofs from THE BOOK by Aigner and Ziegler.
https://en.m.wikipedia.org/wiki/Turán%27s_theorem
