Finding DFS in undirected graph

Question

Consider the following sequence of nodes for the undirected graph given below.

1. a b e f d g c
2. a b e f c g d
3. a d g e b c f
4. a d b c g e f

A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

• 1 and 3 only
• 2 and 3 only
• 2, 3 and 4 only
• 1, 2 and 3 only

---

My attempt :

1. After f is visited, c or g should be visited next.
2. Visited depth
3. Visited depth
4. After c is visited, e or f should be visited next.

Can you explain in more formal way, please?

Answer 1

$1$ is impossible because if the stack consists of $(a,b,e,f)$ (with $f$ at the top), then the next node traversed must be $c$ or $g$, since those are adjacent to $f$ and have not been traversed yet.

$2$ is possible; if the stack consists of $(a,b,e,f,c)$ then we must pop $c$ and then $f$, and can then push $g$ and $d$.

$3$ is possible, as it is a path in the graph.

$4$ is impossible for the same reason as $1$.