Hint: divide the graph into a bipartite graph and double-count on the edge between to parts.

The graph is called Leech tree. We have the following result by Herbert Taylor: H. Taylor, Odd path sums in an edge-labeled tree, Math. Magazine 50 (1977) (5) 258–259. wrote: If there is a Leech tree on $n$ vertices, then $n=k^2$ or $n=k^2+2$.

Let $G=(V,E)$ be the graph in which $V$ is the set of the planets and for each $v_1,v_2\in V$: \[v_1v_2\in E\iff \text{ there exists a flight from } v_1\text{ to } v_2.\]Let $f:E\to\mathbb N$, $f(v_1v_2)$ be the price of the flight from $v_1$ to $v_2$ (price of the edge $v_1v_2$). By the hypothesis $G$ is connected. Because $|E|=|V|-1$ it follows that $G$ is a tree. Therefore for each $x,y\in V$ there is a unique path $p(x,y)$ from $x$ to $y$. We say that a path $p(x,y)$ is even if the total price from $x$ to $y$ is even. Similarly we define an odd path. We construct a coloring $c:V\to\{0,1\}$ as follows let $v\in V$ and let $c(v)=0$; we consider $G$ as a tree with root $v$ and levels $L_1,L_2,\ldots, L_k$; $\forall\, 1\le i\le k$ we color the vertex $u\in L_i$ such that $c(u)=c(n_u)$ if $2\mid f(un_u)$ and $c(u)\ne c(n_u)$ otherwise where $n_u\in N(u)\cap L_{i-1}$. Let $a=|\{v\in V\mid c(v)=0\}$ and $b=|\{v\in V\mid c(v)=1\}|$. Notice that if $v_1v_2\in E$: \[c(v_1)=c(v_2)\iff 2\mid f(v_1v_2).\]Therefore a path $p(v_1,v_2)$ is even iff $p(v_1,v_2)$ has an even numer of edges with odd price iff $c(v_1)=c(v_2)$. Hence we have $ab$ odd paths in $G$. We consider two cases: 1. $\binom{n}2$ is even. Because the prices of the paths from $G$ are $1,\ldots,\binom{n}2$ it follows that we have $\frac12\binom{n}2$ odd paths in $G$. From this and $(2)$ it follows that $ab=\frac12\binom{n}2=\frac{n(n-1)}4$, which implies $4ab=n^2-n$. because $a+b=n$ it follows that $n=n^2-4ab=(a+b)^2-4ab=(a-b)^2.$ Hence $n$ is a perfect square. 2. $\binom{n}2$ is odd. Similarly to the first case we get $ab=\frac12\left(\binom{n}2+1\right)=\frac12\left(\frac{n(n-1)}2+1\right)$, which implies $4ab=n(n-1)+2$. hence $n-2=n^2-4ab=(a+b)^2-4ab=(a-b)^2$, which is a perfect square. Hence \(n\) or \(n-2\) is a square number.