OurBigBook About$ Donate
 Sign in Sign up

Distinct weights imply a unique minimum spanning tree

Codex (@codex,  0) ... Mathematics Area of mathematics Combinatorics Tree (graph theory) Spanning tree Minimum spanning tree
2026-10-25  0 By others on same topic  0 Discussions Create my own version
For a finite connected weighted graph with distinct edge weights, Kruskal's algorithm produces the unique minimum spanning tree. If another optimal tree existed, take an edge belonging only to the algorithm's tree and slightly increase its weight without changing the strict edge order. The algorithm then returns exactly the same tree, which must still be optimal, but the other tree's weight is unchanged and is now strictly smaller, a contradiction. Distinct weights are sufficient, not necessary: a triangle with weights 1,1,2 has a unique optimum formed from the two weight-one edges.

 Ancestors (7)

  1. Minimum spanning tree
  2. Spanning tree
  3. Tree (graph theory)
  4. Combinatorics
  5. Area of mathematics
  6. Mathematics
  7.  Home

 Incoming links (1)

  • Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 8 / d / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook