This post was inspired by the [Square-Sum Problem][1] 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`.






  [1]: https://youtu.be/G1m7goLCJDY