Beautiful Tree

We need construct a tree on vertices $1,2,\dots,n$ such that $S=\sum_{\{u,v\}\in E}uv$ is a perfect square.

The clean move is to stop treating the square as mysterious. We will force the answer to be exactly $n^2$ for every $n\ge5$.

Small cases first:

• $n=2$: the only tree has edge $(1,2)$, so $S=2$, not a square. Answer is $-1$.
• $n=3$: edges $(1,3),(2,3)$ give $3+6=9=3^2$.
• $n=4$: edges $(1,2),(1,3),(1,4)$ give $2+3+4=9=3^2$.

Now the real construction.

Base case

For $n=5$, use the path $5-1-2-3-4.$

Its sum is $5\cdot1+1\cdot2+2\cdot3+3\cdot4=5+2+6+12=25=5^2.$

So $n=5$ works.

How to grow the tree

Suppose we already have a tree on vertices $1,2,\dots,n$ with sum $n^2$.

We want a tree on $n+1$ vertices with sum $(n+1)^2$.

The required increase is $(n+1)^2-n^2=2n+1.$

Add the new vertex $n+1$ using edge $(1,n+1)$. That contributes $n+1$.

Still missing: $(2n+1)-(n+1)=n.$

Now replace edge $(1,n)$ with edge $(2,n)$. The contribution changes from $1\cdot n=n$ to $2\cdot n=2n,$ so the sum increases by exactly $n$.

Perfect. No magic, just accounting. Trees are basically spreadsheets with delusions of grandeur.

Final explicit shape

Unrolling that growth gives a very simple construction for every $n\ge5$:

• include $(1,2)$,
• include $(2,3)$,
• include $(3,4)$,
• include $(1,n)$,
• for every $i=5,6,\dots,n-1$, include $(2,i)$.

This has exactly $3+1+(n-5)=n-1$ edges, so the count is right.

It is connected: vertices $1,2,3,4$ form a path, vertex $n$ is attached to $1$, and every vertex from $5$ to $n-1$ is attached to $2$.

It has no cycle: all the extra vertices are leaves, and the backbone is a tree. So it is definitely a tree.

Now compute the sum:

$S=1\cdot2+2\cdot3+3\cdot4+1\cdot n+\sum_{i=5}^{n-1}2i.$

That is $S=2+6+12+n+2\sum_{i=5}^{n-1}i.$

Since $\sum_{i=5}^{n-1}i=\frac{n(n-1)}2-10,$ we get $S=20+n+2\left(\frac{n(n-1)}2-10\right).$

So $S=20+n+n(n-1)-20=n^2.$

Exactly a square. Nice and boring, which is what you want in constructive problems.

Algorithm

For each testcase:

• if $n=2$, print $-1$;
• if $n=3$, print $(1,3),(2,3)$;
• if $n=4$, print $(1,2),(1,3),(1,4)$;
• otherwise print the construction above.

Complexity

We output $n-1$ edges, so the time is $O(n)$ per testcase and $O(1)$ extra memory.