DFS is too general a term to ascribe any particular complexity to it. I'm surprised Wikipedia claims any particular complexity at all. With the TSP, the problem is determining the global minimum. This provably can't be done without examining most of the possible paths, and this has nothing to do with DFS, it's just a fact.
Since TSP is NP-complete, it's certainly not linear in either |V| or |E|...
