So I am given what is a DFS Tree of an Undirected Graph. Here is the problem:

Now I already know that the answer is (4,3)

But what other edges not listed would be impossible?

Would (3,6) be a valid edge? What about (2,4) or (3,5)

Would it be correct to assume that nodes on different branches of a DFS tree cannot have an edge connecting them?

# Best How To :

The graph `G(V, E)`

, as stated in the original question, is undirected. Consider any pair of nodes `u, v \in V`

such that **there is** an edge `(u, v) \in E`

. Now lets traverse the graph in DFS (depth-first search):

- if we reach
`u`

first, we will eventually visit all nodes that are reachable from `u`

, including `v`

, and therefore `v`

will be a child node of `u`

(or of its child nodes) in the DFS tree;
- if we reach
`v`

first, the case is analogous, as the graph is undirected.

So, for any edge `(u, v) \in E`

, there will be a path in the DFS tree connecting `u`

to `v`

. Now lets see your cases:

1) *Would (3,6) be a valid edge? What about (2,4) or (3,5)?*

- (3, 6): is not a valid edge. If there were such edge, 3 would be a child node of 6;
- (2, 4): is not a valid edge. If there were such edge, 2 would be a child node of 4;
- (3, 5): is not a valid edge. If there were such edge, 3 would be a child node of 5.

2) *Would it be correct to assume that nodes on different branches of a DFS tree cannot have an edge connecting them?*

If there is an edge connecting two nodes `u`

and `v`

in an undirected graph, there will be a path `e1 e2 ... en`

connecting `u`

to `v`

(or `v`

to `u`

) in the associate DFS tree. So, if two nodes from the DFS tree are on different branches, there is no edge inbetween them.