Question $3$: Given a graph G$($V$,$ E$)$ with costs $\{$c$($e$)\}$ over the edges, give an algorithm

that checks if there is a spanning tree of diameter $3.$ And if it exists outputs the

minimum cost spanning tree among all spanning trees with diameter $3.$ Prove your

answer.

Remarks: All the graphs here are without self loops and parallel or anti$-$parallel edges.In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not good. You are not allowed to write programs but can write psudocode.