DFS - Proof of Correctness I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious about how it can be shown that DFS visits all the nodes.
I also googled for it. But it seems that every lecturer do some copy-paste work from this book in their pdf's, so I couldn't find anything useful. 
By DFS we had to show that it found the shortest path. But since DFS does not calculate something like that I have no idea how to prove it.



Off the topic, why are those proofs so important? Throughout the book there are so many lemmas and theorems which can be really boring sometimes. I understand how an algorithm works in 10 minutes, perhaps need another 5 to 10 minutes to understand how to analyse the running time, but then I'm loosing 1 hour just for some useless lemmas. Besides, and worse even, I studied almost 50 proofs/lemmas of different algorithms till now, I never managed to solve one of them by myself. How can I gain the "proving ability"? Is there a systematical way to learn that? I don't mean the Hoare logic way with invariants, rather the informal way described in the book "Introduction to Algorithms". Is there any book which focuses on "how to prove algorithms" and show that in a systematical, introductory way ?
I had the same problem when I was an undergrad. I can see you understand the algorithm. And, to prove that it works is to explain it formally that it works. 

Why we have many proofs ? because we may have algorithms that are not correct, and we need to show that our algorithm is correct and actually work always!. 

Same for the analysis. If we want to prove for example that our algorithm is better than others, then we prove it. You may tell me that we can implement our algorithm and and test it, but this does not consider all the possible cases of input. Therefore, what we do is to prove it. 

(We usually prove the correctness and complexity of an algorithm (which is a measure of its performance)).   

This is just an answer for your second question. For your first question, a hint is to say why we will visit every other vertex if the graph is connected. [Hint: because the graph is connected than for every pair of vertices there is a path.] ...(back to your second question).. if you note here that I am using one fact to prove my original fact (i.e., there is a path connecting every pair of nodes --> DFS is correct). The first fact is clear in our case given the definition of connectivity. In many other cases, it is not clear. So we will need to prove one fact by proving another, and perhaps do that again and again. This is why we have a lot of lemmas and theorems. 

They are boring now. but once you see their magic, you will love them ! As a fun excercise try to solve simple algorithmic problems and prove their correctness and analyses. To verify your answers, re-read your answers. If they convince you, then you are correct. If not, then re-do it again.