Let G(V,E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of G is/are true?

The correct statements are:
1. In every cycle C of G, the edge with the largest weight in C is not in any MST
2. For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST

Here is the detailed step-by-step explanation of why these statements are correct:

1. Explanation of the Cycle Property Statement:

Let $C$ be any cycle in the graph $G$, and let $e$ be the edge in $C$ with the strictly largest weight (since edge weights are unique). We want to prove that $e$ cannot belong to any minimum spanning tree (MST) of $G$.

Suppose, for the sake of contradiction, that there is an MST $T$ that contains the edge $e$. If we delete the edge $e$ from $T$, the tree $T$ is disconnected into exactly two components, say $V_1$ and $V_2$.

Since $e$ is part of the cycle $C$, there must exist at least one other edge $e^{\prime }$ in the cycle $C$ that also connects $V_1$ and $V_2$. Since $e$ is the unique edge with the largest weight in cycle $C$, the weight of $e^{\prime }$ must be strictly less than the weight of $e$:

$\mathrm{weight}\left(e^{\prime }\right)<\mathrm{weight}\left(e\right)$

If we construct a new spanning tree $T^{\prime }$ by removing $e$ and adding $e^{\prime }$, the new tree $T^{\prime }=T-\left\{e\right\}\cup \left\{e^{\prime }\right\}$ remains connected and spans all vertices. However, the total weight of $T^{\prime }$ is strictly less than the total weight of $T$. This contradicts the assumption that $T$ is a minimum spanning tree. Thus, the edge with the largest weight in any cycle $C$ cannot be in any MST.

2. Explanation of the Cut Property (Incident Edges) Statement:

For any vertex $v\in V$, let us define a cut in the graph that separates $v$ from all other vertices. This cut is represented by the partition $\left(\right\{v\},V\backslash \{v\left\}\right)$.

The edges crossing this cut are precisely all the edges incident on the vertex $v$. By the Cut Property of minimum spanning trees, for any cut of a graph, the edge with the minimum weight crossing that cut must belong to the MST. Because all edge weights in the graph $G$ are unique, there is a unique edge $e_{\min }$ incident on $v$ that has the smallest weight among all incident edges.

Since $e_{\min }$ is the unique minimum-weight crossing edge for the cut $\left(\right\{v\},V\backslash \{v\left\}\right)$, it must be included in every MST of $G$.