Question 4: Let\ be a connected undirected graph with distinct positi…

Let
be a connected undirected graph with distinct positive edge weights.Consider

a partition (cut) of the vertex set
into two non-empty subsets
and
such that:

•
, and

•

Let
be the minimum-weight edge among all edges that cross this cut, i.e., and

.
Which of the following statements is/are true?

I. For every pair of nodes
such that
and
, the edge
must lie on the shortest

path from
to
.

II. The edge
must be part of the minimum spanning tree (MST) of
.