Every connected graph contains a spanning tree: subgraph that both connects all nodes and is a tree. If we minimize the sum of the edge weights we get a minimum spanning tree. There are two famous algorithms to compute this; we will focus on Kruscal’s algorithm for this class.