Depth First Search proofs

I am trying to prove that the depth first search algorithm covers all vertices when the algorithm is performed on a connected graph.

I have already proved that the output graph is connected and that it is acyclic so these things can be assumed in this proof. Whether or not it will aid in the proof, i don't know. I can visualize it in my head quite easily how the algorithm covers all vertices but getting it down on paper isn't as easy. I've tried using induction but I think i'm making too many assumptions that I shouldn't be making. I can't find any sources which go over a proof of the kind i'm looking for so any help on directing me to a source, or otherwse, would be much appreciated!

Induction works, doesn't it? The result is trivial for $n=1$. Then assume we have that for a graph with $n$ vertices, we hit each node $N$ at step $k_N$ of the depth-first algorithm. Then if we add a node, it must be connected to something; say it's connected to node $N$. But then we hit the new node at step $k_N+1$, and then all subsequent $k_m$ are set to $k_{m+1}$ for $m>N$, and it works still.

Does that not work? It's quite late at night, so I may have missed something.

Thanks for the reply, and yes that does make sense, that's something along the lines of what I did but I'm just wondering, if (for graph G with k vertices and graph H with k+1 vertices) i'm allowed to assume that taking away a vertex from H makes it equivalent to G. I know it makes sense that G is equivalent to H with 1 less vertex in this context but I'm trying to be very thorough with the proof and drawing conclusions straight away like that seems a bit of a jump.