- #1

ciphone

- 3

- 0

## Homework Statement

(a) If e is part of some MST of G, then it must be a lightest edge in some cutset of G.

## Homework Equations

Cut property

## The Attempt at a Solution

When the cutset has just one edge then yes it's true obviously. I am think I can do this by contradiction. Assuming e_i is part of some MST of G and e_i is not the lightest edge in any cutset. If this is true then, in every cutset, there exists an edge e_k such that e_k>e_i. I don't know how to go from here

*The cut property says For any*

*cut*C

*of the graph, if the weight of an edge*

*in the cut-set of*C

*is strictly smaller than the weights of all other edges of the cut-set of*C

*, then this edge belongs to all MSTs of the graph.*

It doesn't say anything about the larger edges in the cut