The Hawking Space Agency operates $n-1$ space flights between the $n$ habitable planets of the Local Galaxy Cluster. Each flight has a fixed price which is the same in both directions, and we know that using these flights, we can travel from any habitable planet to any habitable planet. In the headquarters of the Agency, there is a clearly visible board on a wall, with a portrait, containing all the pairs of different habitable planets with the total price of the cheapest possible sequence of flights connecting them. Suppose that these prices are precisely $1,2, ... , \binom{n}{2}$ monetary units in some order. prove that $n$ or $n-2$ is a square number.
Problem
Source: Komal A. 722.
Tags: combinatorics
12.05.2018 07:46
Hint: divide the graph into a bipartite graph and double-count on the edge between to parts.
30.07.2018 16:58
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$.
21.05.2023 14:50
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.