The comment was too short.
Your correctness proof is hardly there. I also don't know what do you mean by 'comparisons' and where from you got $2|E|$. On the other hand, this is a correct algorithm given you have a connected graph. Your comment explains what to do in disconnected case, but then you could just apply it, after all, one searches for the connected components with DFS (and those two DFSes could be just one). Moreover, one can do initialization faster, the $|V|$ part of complexity should come from the fact that in the worst case you will have to visit (or at least take care in some way) all the vertices. Of course, if you have initialization done this way, you ought to mention it (as you did; besides this is not a big fault, usually you need to read the graph from some kind of input and this is where you can initialize your arrays/maps).
Finally, this is a fine attempt, you shouldn't be discouraged. There are some issues, but I would be glad if my students had enough patience and precision to work it out as you did.
As for suggestions for complexity, the best way is to express the number of operations in your algorithm depending on some global properties, like "my algorithm visits every vertex at most 42 times and every edge at most 78" or "for every edge it does at most $|V|^{567}$ operations" and so on.
As for suggestions for correctness, one usually splits the proof into two parts: "if cycle exists, then my algorithm will return true" (or "if my algorithm returns false then graph is a forest"), and "if my algorithm returns true, then cycle exists" (or "if cycle doesn't exists, my algorithm will return false"). This is not the fastest way, but it is very easy to do serious mistakes if you prove both implications at the same time.
I hope you will find my advice usefull.
Another way of saying this: for some $k$, $1 \le k \le \lfloor n/2 \rfloor$, there is only one node at distance $k$ from $s$ (otherwise, counting $s$, $t$ and at least $2$ nodes at each $k$ you'd nave at least $2 + 2 \lfloor n/2 \rfloor > n$ vertices).
Every path from $s$ to $t$ must pass through a node at distance $k$ from $s$, so if you delete the only such node you no longer have such a path.
Best Answer
Yes, DFS trees are not unique - your example serves as enough. You can consider some cycle graph and notice there are at least two ways to traverse the cycle using DFS, starting at a given vertex.
When you use a linked list adjacency structure, the neighbors are automatically assigned priority when you add their edges to the graph. So the DFS will just use these priorities (i.e. select the next neighbor of the vertex) and give the same representation every time. In general this would give different traversals depending on the order edges are added.
Someone using an adjacency matrix would have to do DFS based on the order the vertices are assigned (you have to label each vertex with a number).