$($Uninformed search; $24$ points$)$

$($a$)[14$ points$]$ Construct a search graph with no more than $10$ nodes for which all of the following are true:

i$.$ Least$-$cost search returns an optimal solution.

ii$.$ Depth$-$first search returns the highest$-$cost solution.

iii. Breadth$-$first search returns a solution whose cost is strictly less than the highest$-$cost solution and strictly more than the least$-$cost solution.

Note that this means your search graph must have at least $3$ solution paths of differing costs. $($You are allowed to have multiple goal nodes.$)$ Be sure to include and formally describe each component of the search graph. If necessary for concreteness, specify the order in which successor paths are added to the frontier by each algorithm.

$($b$)[5$ points$]$ List the paths that are removed from the frontier by a depth first search of the problem you specified in part $(1$a$),$ in the order in which they are removed. The algorithm should stop as soon as it returns a solution.