  We study graph-theoretic properties of the trace of a random walk on a random
graph. We show that for any $\varepsilon>0$ there exists $C>1$ such that the
trace of the simple random walk of length $(1+\varepsilon)n\ln{n}$ on the
random graph $G\sim G(n,p)$ for $p>C\ln{n}/n$ is, with high probability,
Hamiltonian and $\Theta(\ln{n})$-connected. In the special case $p=1$ (i.e.
when $G=K_n$), we show a hitting time result according to which, with high
probability, exactly one step after the last vertex has been visited, the trace
becomes Hamiltonian, and one step after the last vertex has been visited for
the $k$'th time, the trace becomes $2k$-connected.
