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.