  It is a celebrated fact that a simple random walk on an infinite $k$-ary tree
for $k \geq 2$ returns to the initial vertex at most finitely many times during
infinitely many transitions; it is called transient. This work points out the
fact that a simple random walk on an infinitely growing $k$-ary tree can return
to the initial vertex infinitely many times, it is called recurrent, depending
on the growing speed of the tree. Precisely, this paper is concerned with a
simple specific model of a random walk on a growing graph (RWoGG), and shows a
phase transition between the recurrence and transience of the random walk
regarding the growing speed of the graph. To prove the phase transition, we
develop a coupling argument, introducing the notion of less homesick as graph
growing (LHaGG). We also show some other examples, including a random walk on
$\{0,1\}^n$ with infinitely growing $n$, of the phase transition between the
recurrence and transience. We remark that some graphs concerned in this paper
have infinitely growing degrees.
