Guichard-Combinatorics-Graph-Theory · Problem 5.6.1

Graph Theory

Mathematics — Probability · optimal-spanning-trees

Problem

Kruskal's Algorithm is also a greedy algorithm that produces a minimum cost spanning tree for a connected graph

G

. Begin by choosing an edge in

G

of smallest cost. Assuming that edges

e_1, e_2, \ldots, e_i

have been chosen, pick an edge

e_{i+1}

that does not form a cycle together with

e_1, e_2, \ldots, e_i

and that has smallest cost among all such edges. The edges

e_1, e_2, \ldots, e_{n-1}

form a spanning tree for

G

. Prove that this spanning tree has minimum cost.