Combinatorics and Graph Theory · Problem 5.6.2

Graph Theory — David Guichard

Mathematics — Combinatorics · optimal-spanning-trees

Problem

Prove that if the edge costs of

G

are distinct, there is exactly one minimum cost spanning tree. Give an example of a graph

G

with more than one minimum cost spanning tree.