How to prove that a depth-first algorithm labels every vertex of G? I understand exactly how a depth-first search/algorithm works. You start at the root, and then go to the left most node, and go down as far as you can until you hit a leaf, and then start going back and hitting the nodes you did not hit before. 
I get how it works, and I can see that if a graph is connected than it is going to hit every vertex, but I do not know how to really prove it. It seems as simple that if the graph is connected, then it is going to hit every vertex, but I know it can't be that simple... 

If the search didn't visit all vertices, there is a non-empty set of vertices that it visited and a non-empty set of vertices that it didn't visit. Since the graph is connected, there is at least one edge between a visited vertex and a non-visited vertex. But when the algorithm reached the visited vertex, it successively visited each of its neighbours, each time returning after finitely many steps (since each of the finitely many edges is traversed at most twice), and thus also visited the non-visited vertex. The contradiction shows that all vertices were visited.
