$(50$ points$)($both CSCE$423$ and CSCE $823)$ Graph G is shown below.

$1\mathrm{.}1$ Graph $G=(V,E)$ Please till in the blanks:

Since it's an undirected graph, $(1,2)$ and $(2,1)$ are the same edge, you only need to write it once. $*$

$1\mathrm{.}2$ Let's apply Kruskal algorithm below.

Please first write down sorted edge list E$-$sorted$=$

Specify the steps of adding edges or rejecting edges for generating an MST$.$

$1\mathrm{.}3$ Please draw the tree structure for MST below. What is the total weight for the MST you have

generated from above?

$1\mathrm{.}4$ Use Prim's algorithm, to fill in the following table. It should be dane in $6$ steps.

$1\mathrm{.}5$ Please specify the light edge for each of the following cuts.

$1\mathrm{.}6$ Among those six cuts in question $1\mathrm{.}5,$ which ones were appeared during the procedure of the Prim's

algorithm $($from question $1\mathrm{.}4)?$