The following statements may or may not be correct. In each case, either prove it

$($if it is correct$)$ or give a counterexample $($if it isn't correct$).$ Always assume that

the graph G$=($V$,$E$)$ is undirected and connected. Do not assume that edge

weights are distinct unless this is specifically stated.

$($a$)$ If graph G has more than $|$V$|-1$ edges, and there is a unique heaviest

edge, then this edge cannot be part of a minimum spanning tree.

$($b$)$ If G has a cycle with a unique heaviest edge e$,$ then e cannot be part of

any MST$.$

$($c$)$ Let e be any edge of minimum weight in G$.$ Then e must be part of some

MST$.$

$($d$)$ If the lightest edge in a graph is unique, then it must be part of every

MST$.$

$($e$)$ If e is part of some MST of G$,$ then it must be a lightest edge across some

cut of G$.$

$($f$)$ If G has a cycle with a unique lightest edge e$,$ then e must be part of

every MST$.$

$($g$)$ The shortest$-$path tree computed by Dijkstra's algorithm is necessarily an

MST$.$

$($h$)$ The shortest path between two nodes is necessarily part of some MST$.$

$($i$)$ Prim's algorithm works correctly when there are negative edges.

$($j$)($For any r $>0,$ define an r$-$path to be a path whose edges all have weight

$$ r$.)$ If G contains an r$-$path from node s to t$,$ then every MST of G must

also contain an r$-$path from node s to node t$.$

Show how to find the maximum spanning tree of a graph, that is$,$ the spanning

tree of largest total weight.

solve these questions $($design and analysis of algorithms$)$