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.


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 with 17 vertices and 16 edges

Basic Properties


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

image.png

Indirect Cycle Path

image.png


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

image.png

Checking for a cycle


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

image.png

Key Property


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>