Date: March 2, 2026
Topic: Minimum Spanning Tree
<aside>
📌 SUMMARY:
A MST is an undirected graph with weights $w(e)$
****To find the MST, we can use Kruskal’s algorithm, where we first sort the weights of the edges and add them into the MST by increasing weights
Vertices that already can be reached through some prior pathings will not have their edges added to avoid cycles
</aside>
Recall
Notes
Minimum Spanning Tree
Input
Undirected graph $G=(V,E)$ with weights $w(e)$ for $e \in E$
Goal
Find the minimal size connected subgraph (spanning tree) of min weight.
- Find the min. weight spanning tree of $G$
- For a tree $T \subset E$, its weight $w(T)$ is the sum of the weights of of the edges in that tree (i.e., $w(T) = \sum_{e \in T} w(e)$)
A connected graph is a tree if the number of edges is 1 less than the number of vertices
$|E| = |V| - 1$
Tree Properties

A tree with 17 vertices and 16 edges
- A tree is a connected, acyclic graph
Basic Properties
- A tree on $n$ vertices has $n-1$ edges → if we have more edges, then we get a cycle
- In a tree, there is exactly one path between every pair of vertices
- Any connected $G=(V,E)$ with $|E| = |V| -1$ is a tree → any graph that has the number of edges 1 less than the number of vertices is a tree
We continuously add edges of increasing weight into the MST, and if 2 vertices are already reachable (can be indirectly), then we don’t connect them as this leads to a cycle.
Greedy Approach for MST
Adding Edges

- We build the MST one edge at a time, and consider the edges by increasing weight
- Start with the first edges of lowest weight ($1$ in this graph)
- Addition is shown by the red squiggly line
- As we find more edges by increasing weight, we only add them into the MST if possible (doesn’t create cycle)
- In the above we don’t add the edge with weight 6 into the MST as this will create a cycle.
Indirect Cycle Path

- We cannot directly connect vertices $v$ and $w$ as an indirect path already exists
- Connecting them through the edge with weight $12$ leads to a cycle
Kruskal’s algorithm takes $O(m \log n)$ time to carry out, mainly due to the sorting of the edges by increasing weight.
To determine if we should add an edge between 2 vertices into the subgraph, we use the Union-Find data structure to check if a path between them already exists.
Kruskal’s Algorithm
def kruskals(G)
'''
Input: Undirected graph G = (V,E) with weights w(e)
'''
1. Sort the edges E by increasing weight (e.g., mergesort)
2. Set X = null -> use set X to keep track of the edges inserted so far into the MST
3. For e = (v,w) in E, we go through the edges in order of increasing weight
if X U e does not have a cycle (adding this edge does not create a cycle):
then X = X U e (add the edge into X)
4, Return(X) -> this will be the MST
Analysis

- To sort by increasing weight, it takes $O(m \log n)$ time where $m$ is num. edges and $n$ is num. vertices
- Using Union-Find, we can check if two vertices already exist in the same component. This takes $O(\log n)$ time.
union(u, v) says: “these two vertices belong to the same component, so merge their sets.”
- After doing this for all relevant edges, each connected component becomes one set.
find(x) returns the representative/root of the set containing $x$.
- So if
find(u) == find(v), then $u$ and $v$ are in the same component.
Checking for a cycle
- Look at the sub-graph on the set of edges in $X$ — subgraph is $(V,X)$
- In the subgraph, $c(v)$ is the component containing $v$ and $c(w)$ the component containing $w$
- To see if we should add an edge, check if there is already a path between $v$ and $w$
- This means that $v$ and $w$ are already in the same component
- Only if they are in different components ($c(v) \neq c(w)$) then do we add the edge $e$ to $x$
- This can be determined with the Union-Find data structure
- Union-Find takes $O(\log n)$ for each check operation — check whether the component containing $v$ and component containing $w$ are the same or not
- We only unite 2 sets if they are separated, this prevents cycles
- Merge operation takes $O(\log n)$ time to merge the component containing $v$ and the component containing $w$ as we add edge $e$ into $X$
if we take a subset of edges that are part of an MST, and we take an edge crossing from $S$ to $\bar{S}$ of min. weight, we can safely add this edge in and $X$ will still be part of the MST.
Kruskal’s Correctness

- Assume by induction that the subgraph $X$ is correct so far, $X \subset T$ where $T$ is a MST
- If we add the edge $e=(v,w)$ to $X$, then $X \cup e \subset T'$ where $T'$ is an MST
Key Property
- Let $S = c(v)$ (the circled components)
- $\bar S$ is the complement of $S$, so it holds the rest of the vertices
- The key property is that for the current subset $X$, it has no edges that connect $S$ to $\bar{S}$
- $S$ is a maximal set, so nobody in $\bar{S}$ is connected to anybody in $S$, thus there are no edges from $X$ going from $S$ to $\bar{S}$
- In general, if we take a subset of edges that are part of an MST, and we take an edge crossing from $S$ to $\bar{S}$ of min. weight, we can safely add this edge in and $X$ will still be part of the MST
Date: March 3, 2026
Topic: Cut Property
<aside>
📌 SUMMARY:
Cuts are where edges cross from one component to another (e.g., $S \leftrightarrow \bar{S}$).
We build the partial solution $X$ to the MST edge-by-edge, and so it may be possible for multiple MSTs to exist due to duplicate edge weights.
Thus we may construct an MST $T'$ that has the same weight as the MST $T$ but comprised of different edges.
We can safely remove edges (to prevent cycles) from $T$ and add $e^*$ to construct $T'$ since we replace an edge from $T$ in the cut with an equal cost edge from the cut.
</aside>