Other edges which is given in option will present based on which order you have traversed

Dark Mode

1 vote

$G$ is an undirected graph with vertex set $\{v1, \ v2, \ v3, \ v4, \ v5, \ v6, \ v7\}$ and edge set $\{v1v2,\ v1v3,\ v1v4\ ,v2v4,\ v2v5,\ v3v4,\ v4v5,\ v4v6,\ v5v6,\ v6v7\ \}$. A breadth first search of the graph is performed with $v1$ as the root node. Which of the following is a tree edge?

- $v2v4$
- $v1v4$
- $v4v5$
- $v3v4$

0 votes

V1 is adjacent to V2,V3,V4

so queue state will be

V1 | V2 | V3 | V4 | V5 |

After V1 is popped the queue will contain V2 V3 V4 and V5

Note: the above elements can appear in any order after V1

so, V4 can be popped first and you may think that the answer is V4V5. But here V2 V3 and V5 can also be popped first. so V4V5 may be an edge which will not be included in the BFS tree(as V2 also has an edge to V5).

But V1V4 edge will always be included in the BFS tree as we have taken V1 as the root.

So, answer is b)V1V4