This post was inspired by the Square-Sum Problem presented in Numberphile by Matt Parker.

He asked about Hamiltonianness for $n=2$, and we ask about connectedness for all $n \in \mathbb{N}^*$.

Given $n \in \mathbb{N}^*$, let $\mathcal{G}_n$ be the graph $(\mathbb{N}^*,\{ \{a,b\} \ | \ a+b \in S_n\})$, with $S_n = \{r^n | r\in \mathbb{N} \}$ .

**Question**: Is $\mathcal{G}_n$ connected?

*Checking*: It is true for $n \le 5$.

*Proof*: For any $a \in \mathbb{N}^*$, there is $r\in \mathbb{N}$ such that $r^n \le a < (r+1)^n$. Then, $\{a,(r+1)^n-a\}$ is an edge of $\mathcal{G}_n$. Now, $(r+1)^n-a<a$ iff $(r+1)^n<2a$, which occurs if $(a^{1/n}+1)^n < 2a$.
Below the table for $a_n$, the greatest $a \in \mathbb{N}^*$ such that $(a^{1/n}+1)^n \ge 2a$, for $n \le 5$:

$$\begin{array}{c|c}
n&1&2&3&4&5 \newline \hline
a_n&1&5&56&780&13755
\end{array}$$
It follows that as long as $a>a_n$, there is $b<a$ such that $\{a,b\}$ is an edge of $\mathcal{G}_n$. So we are reduced to prove that the set of vertices $\{ 1,2, \dots,a_n \}$ is covered by a connected component.

For so, we wrote the following SAGE program:

```
cpdef PowerSumGraph(int a, int s, int n):
cdef int i,j,r,t
G=Graph({})
for i in range(1,a):
r=i**(1/n)
for j in range(r,s):
t=j**n-i
if t>0 and i<>t:
G.add_edge(i,t)
return G.is_connected()
```

The result follows by the (minimal) computation below. $\square$

```
sage: PowerSumGraph(13,6,2)
True
sage: PowerSumGraph(108,7,3)
True
sage: PowerSumGraph(2008,9,4)
True
sage: PowerSumGraph(49355,11,5)
True
```

The case $n=6$ works also, by the following (non-minimal) computation and $a_6 = 296476$.

```
sage: PowerSumGraph(1500000,13,6)
True
```

The case $n=7$ is beyond my laptop capacity. For $n \ge 8$, the program should be modified because it would deal with integers beyond $2^{31}-1$, the maximum value for variables declared as `int`

.