$($Modified from a problem in Algorithms by Jeff Erickson$)$

Note: this problem will be graded manually.

Let $G$ be a connected undirected graph. Suppose we start with three coins on three arbitrarily chosen vertices

of $G,$ and we want to move the coins so that they lie on the same vertex using as few moves as possible. At

every step, each coin must move to an adjacent vertex and all coins move at the same time.

Our goal is to analyze an algorithm that finds the shortest solution to the puzzle.

Algorithm

Step $1$: Build the graph $H$

The graph $H$ will represent to positions of all three coints. The vertices of $H$ are of the form $(u,v,w)$ where

$u,v$ and $w$ are vertices of $G.$

Given any combination of edges $u-u^{\text{'}},v-v^{\text{'}}$ and $w-w^{\text{'}}$ in $G$ there is an edge in $H$ from $(u,v,w)$ to

$(u^{\text{'}},v^{\text{'}},w^{\text{'}}).$

Step $2$: Perform BFS search on $H$

Assume that the three coins start at positions $a,b$ and $c.$ We will perform BFS search on $H$ starting at $(a,b,c).$

We will continue until we reach a point where all three coins are at the same location. This is a vertex of the

form $(u,u,u)$ where all three vertices in $G$ are the same. The depth of this vertex is the length of the solution.

Answer the following questions about the algorithm. You may assume that $G$ has $n$ vertices and $m$ edges.

Step $1$

How many vertices and edges are in the graph $H?($Your answer should be in terms of $n$ and $m.)$

How long does step $1$ of the algorithm take? $($You answer should be in terms of $n$ and $m$ and be written using

big$-$O notation.$)$

Step $2$

How long does step $2$ of the algorithm take? $($You answer should be in terms of $n$ and $m$ and be written using

big$-$O notation.$)$

Overall runtime

How long does it take for the algorithm to run? $($You answer should be in terms of $n$ and $m$ and be written

using big$-$O notation.$)$

please describe the clear explanation.