Why is tracking visited nodes important when traversing a graph?

A graph may contain a cycle: a path that starts and ends at the same vertex. Walk along such a path keeping no record of where the traversal has already been, and it returns to that vertex and sets off around the loop again. Nothing inside the algorithm stops it. A breadth-first queue keeps receiving work it has already done, and a depth-first recursion runs until the call stack overflows. Marking is what makes the traversal terminate at all, which is why the standard formulation of depth-first search marks every vertex in the order it is discovered and finished.

The mark sits beside the graph, not in it: a hash set of identifiers, an array of flags, one colour per vertex. Nothing is deleted, so a traversal never removes nodes from the structure it is reading. Nor does it rewrite the graph into a tree, although the discovery edges do form a spanning forest while every back edge and cross edge stays where it was. Skipping the marking is safe only on input already known to be acyclic, and that is exactly the assumption a graph does not give you.