A simple undirected graph G is COMPLETE if every pair of distinct vertices in G are adjacent. Suppose G is such a graph with n vertices. Then

Question $8$Answer

a$.$

In DFS$($G$)$ there are $($n$1)($n$2)/2$

back$-$edges,, and every node of the DFS$-$tree has at most one child

b$.$

In BFS$($G$)$ the root of the BFS$-$tree has n$1$

children, and there are $\backslash$Theta $($n$2)$

BFS back$-$edges

c$.$

In BFS$($G$)$ height of the BFS$-$tree is O$(1)$

and there are O$($n$)$

non$-$tree edges

d$.$

In DFS$($G$)$ every node in the DFS$-$tree has at most n$1$

children, there are $\backslash$Theta $($n$)$

DFS back$-$edges and $\backslash$Theta $($n$2)$

cross$-$edges