A minimum spanning tree connects every node while minimizing total edge weight. This lesson pins the weighted graph and shows the unique tree that the recomputed algorithms certify.
highlighted = computed this step
Pinned graph
The graph has 6 nodes and 9 weighted edges. Motivation: before any greedy step is trusted, the instance has to be fixed and auditable.
∣V∣=6∣E∣=9
Distinct weights
The smallest edge weight is 1 and the largest is 9. Why: distinct weights make the minimum spanning tree unique here, so a certificate has one tree to certify.
minw=1maxw=9
Tree cost
The minimum spanning tree has 5 tree edges and total weight 19. Interpretation: it connects every node without a cycle, and the number shown is the exact sum of the selected edge weights.
w(T)=19
Diagram note
Certificate note: the diagram marks tree edges by role; non-tree edges remain available but are not in the recomputed MST. Pixel positions are rounded for layout; every number shown is exact.
distinct weights give a unique MST on this instance