### NAMES:

### LOGINS:

### PRECEPTS:

###
COS 226 Exercises on MST

*Reference: Chapter 4.3 in Algorithms, 4th edition.*

**1. **
Consider the following weighted undirected graph.

List the edges in the MST in the order in which they are discovered by
Prim's algorithm, starting the search at `A`.
Since all edge weights are distinct, identify each edge by its **weight**
(instead of its endpoints).

--- --- --- --- --- --- --- ---

**2. **
Repeat question 1 for Kruskal's algorithm.

--- --- --- --- --- --- --- ---

**3. **
Explain briefly, but rigorously, why running Kruskal's algorithm
with the *squares* of the weights yields an MST
on the original network (with the original weights).
Assume all weights are nonnegative.