The following statements may or may not be correct, In each case, either prove it (if it is correct) or give a counter-example (if it isn’t correct). Always assume that the graph $\mathbf{G}\mathbf{=}\left(V,E\right)$is undirected. Do not assume that edge weights are distinct unless this is specifically stated.

1. If a graph G has more than $\left|V\right|\mathbf{-}\mathbf{1}$edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree.
2. If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
3. Let e be any edge of minimum weight in G. Then e must be part of some MST.
4. If the lightest edge in a graph is unique, then it must be part of every MST.
5. If e is part of some MST of G, then it must be a lightest edge across some cut of .
6. If G has a cycle with a unique lightest edge e must be part of every MST.
7. The shortest-path tree computed by Dijkstra’s algorithm is necessarily an MST.
8. The shortest path between two nodes is necessarily part of some MST.
9. Prim’s algorithm works correctly when there are negative edges.
10. (For any $\mathbf{r}\mathbf{>}\mathbf{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.

Consider the undirected graph with weighted edges and the subgraphs.The sum of the weights of all the edges in the tree is the spanning-tree cost. The tree with the minimum spanning cost is known as the minimum spanning tree.

(a)

Consider the undirected graph $\mathrm{G}=\left(\mathrm{V},\mathrm{E}\right)$, with more than $\left|\mathrm{V}\right|-1$edges and a unique heaviest edge. The unique heaviest edge cannot be a part of a minimum spanning tree.

Consider the below graph as the counter-example:

In the above diagram, the edge with a weight of 10 is the unique heaviest edge. The minimum spanning tree of the above graph will not accept the heaviest edge since it is not included in the cycle.

Therefore, the provided statement is False, as shown by the counter-example.

(b)

Consider the undirected graph G with the unique heaviest edge e. The graph G has the cycle with a unique heaviest edge as follows:

In the above diagram, the edge D to E is the unique heaviest edge. The edges A, B, C, and D form the cycle. The cycle is the minimum spanning tree of the graph that does not include the unique heaviest edge.

Therefore, the provided statement is True, and the graph proves it.

(c)

Consider the graph G that has the edge e that has minimum weight. Consider the graph given in the diagram below. The edge B to A has a minimum weight of 2.

In the above graph, the minimum spanning tree includes the edge B to the minimum weight edge of the graph.

Therefore, the minimum edge e in a graph must be part of some MST, and the graph diagram proves it.

(d)

Consider the graph G with the lightest unique edge.

The above graph has the lightest unique edge D to E with weight 1. The graph’s minimum spanning tree will include the edge D to E with weight one since the least minimum weight of the graph is 1.

Therefore, the unique lightest edge of the graph must be part of every true MST that is proved by the graph.

(e)

Consider the graph G with the lightest edge across some cut of G

In the above graph, the minimum edge e of the minimum spanning tree is A to B. The edge D to E is the lightest edge e^' across the cut. The minimum edge e can be replaced by the lightest edge across the cut e^' and obtain a smaller minimum spanning tree.

Therefore, the Lightest edge across some cuts is the part of some MST that is True, which is proved by the graph.

(f)

Consider the graph G with the lightest unique edge.

Consider the above graph that has the lightest unique edge e is B to C. The bold edge with weight 1 is not the part of the MST but the lightest edge in the cycle ABCD.

Therefore, the statement is False, and a counter-example is provided.

(g)

Consider the graph G as follows:

In the above graph, the shortest path from A to D by Dijkstra’s algorithm is A-D. The edge A-D is the heaviest edge of the graph. Dijkstra’s algorithms will use the heaviest edge of a cycle; it is on the shortest path from the source to the destination.

Therefore, the provided statement is False, and the counter-example proves it.

(h)

Consider the graph G as follows:

In the above graph, the shortest path between the source and the destination is A-D . The minimum spanning tree of the graph is ABCD. The shortest path between the source and destination is not part of any MST.

Therefore, the provided statement is False, and the counter-example proves it.

(i)

Consider the graph that has negative edges. Prim’s algorithm always adds the lightest edge between the visited vertices and the unvisited vertices, which is the lightest edge of this cut.

Therefore, Prim’s algorithm correctly works when there are negative edges.

(j)

Suppose that a graph G contains an r-path from the source to destination but that there is an MST T of G that does not contain an r-path from source to destination. ThenT contains a path from source to destination with an edge e of weight ${\mathrm{w}}_{\mathrm{e}}\ge \mathrm{r}$ . Consider the partition of vertices made by removing e from T. One vertex e^' of the r-path must be along this cut, as the r-path connects source and destination. Since ${\mathrm{w}}_{{\mathrm{e}}^{\text{'}}}<\mathrm{r}$ , swap e^' for e to get a spanning tree that is lighter than T, a contradiction.