Properties of MST in an Undirected Graph

You have a simple undirected graph G = (V, E) where each edge has a distinct weight. Consider an edge e as part of this graph. Determine which of the given statements regarding the Minimum Spanning Trees (MSTs) of G is/are TRUE.

Input:

Statements regarding MSTs of G: I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

Output:

Determine which statements are true or false.

Example:

Input:

G = (V, E), where each edge has a distinct weight

Output:

Statement I is true. Statement II is true.

Constraints:

• The graph G is undirected and simple.
• All edge weights are distinct.

Note:

The lightest edge concept in a cycle ensures its inclusion in every MST, while the heaviest edge in a cycle is excluded from every MST.