Reference no: EM133703180

Question: A connected graph is a graph with only one component. That is, every vertex is reachable from every other vertex. In class, we discussed how a con- nected graph may have multiple DFS trees, even when starting at the same node. Give an example of a connected graph with at least 5 nodes such that for each node v, the following statement is true: explore(G, v) is guarantee to give the same recursion tree regardless of which neighbor is chosen for re- cursion at each step. (Note that this does not require that explore(G, v) and explore(G, u) give the same recursion tree for two different nodes v and u.) Two recursion trees are considered the 'same' even if the location of children are swapped: for example, a tree with root A, left child B, and right child C is the same as a tree with root A, left child C, and right child B. These trees are different from a tree with root A, left child B, and C as a child of B.