Problem $2.$ Give an example of a simple, undirected, and unweighted graph $G(V,E)$ that has a single source

shortest path tree which a breadth$-$first traversal will NOT return for any ordering of its vertices. Your answer

must

$($a$)$ Provide a drawing of the graph G$.[$Note: We have provided TikZ code below if you wish to use IATEX to

draw the graph. Alternatively, you may hand$-$draw $G$ and embed it as an image below, provided that $($i$)$

your drawing is legible and $($ii$)$ we do not have to rotate our screens to grade your work.$]$

$($b$)$ Specify the single source shortest path tree $T=(V,E_T)$ by specifying $E_T$ and also specifying the root $sinV.$

$[$Note: You may again hand$-$draw this tree. If you wish, you may clearly mark the edges of $T$ on your

drawing of $G.$ Please make it easy on the graders to identify the edges of $T.]$

$($c$)$ Include a clear explanation of why the breadth$-$first search algorithm we discussed in class will never produce

$T$ for any orderings of the vertices.

Answer.