Minimal Spanning Trees (HSC SSCE Mathematics Standard): Flashcards

Connected graph, no cycles, loops, or multiple edges

$n - 1$ edges

Tree connecting all vertices of a graph

Spanning tree with minimum total edge weight

Find minimum spanning tree in weighted graph

Choose any starting vertex

Lowest weight edge that doesn't create a cycle

All vertices included in tree

Path exists between any two vertices

Cannot return to vertex by following edges