> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-2025/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-2025/25.-minimum-spanning-trees/25.4-chapter-summary.md).

# 25.4 Chapter Summary

In this chapter, we learned about Minimum Spanning Trees and the Cut Property:

* **MST:** the lightest set of edges in a graph possible such that all the vertices are connected and acyclic. 
* **The Cut Property**: given any cut, the minimum weight crossing edge is in the MST.
  * *Cut*:  an assignment of a graph’s nodes to two non-empty sets 
  * *Crossing Edge:* an edge which connects a node from one set to a node from the other set.

We also learned about how to find MSTs of a graph with two algorithms: 

* **Prim's Algorithm**: Construct MST through a mechanism similar to Dijkstra's Algorithm, with the only difference of inserting vertices into the fringe not based on distance to goal vertex but distance to the MST under construction. 
  * *Runtime*: $$O((|V| + |E| )log(|V|))$$
* **Kruskal's Algorithm**: Construct MST by first sorting edges from lightest to heaviest, then add edges sequentially if no cycles are formed until there are V - 1 edges.
  * Runtime: 
    * $$O(|E| log |E|)$$ (unsorted edges)
    * $$O(|E| log\* |V|)$$ (sorted edges)