Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Find a minimum spanning tree by removing costliest cycle edges

Use when: you have a connected, weighted graph and need its cheapest spanning tree

Goal: a spanning tree using only the graph's own edges, connecting every vertex at the lowest possible total weight

Taught in Spanning trees

Quick recipe

  1. Count the edges a spanning tree must remove
  2. Find a cycle still present in the graph
  3. Remove the costliest edge in that cycle
  4. Repeat until no cycle remains, then confirm the edge count
  1. 1

    Compute (edges of G) minus (n-1), using the tree edge-count theorem for the n-1 part. This tells you the total number of edges to remove.

    Example

    With 5 vertices and 6 edges, a spanning tree needs 5-1=4 edges, so exactly 6-4=2 edges must be removed.

    Why: knowing the target edge count in advance tells you exactly when to stop removing edges.

  2. 2

    Look for a closed loop of edges, a path that starts and ends at the same vertex without reusing an edge. If no cycle remains, the graph is already a tree.

    Example

    Among edges AB, AC, BC, BD, CD, DE, the edges AB, AC, BC form a triangle among A, B, C, a genuine cycle.

    • at least one cycle remains — continue to Step 3.
    • no cycle remains — the graph is already a spanning tree; stop here.

    Why: removing an edge that lies on no cycle would disconnect the graph, so only a cycle edge is ever safe to drop.

  3. 3

    Compare the weights of every edge in the cycle found in Step 2, and delete only the single most expensive one.

    Example

    In the cycle AB{=}4, AC{=}2, BC{=}1, the costliest edge is AB{=}4; remove it and keep AC and BC.

    Why: deleting the most expensive cycle edge can never disconnect the graph, since the cycle's other edges still connect the same vertices, and it keeps the total weight as low as possible.

  4. 4

    Return to Step 2 with the graph as it now stands. When no cycle remains, count the edges left and check that count against Step 1's target.

    Example

    After removing AB, the triangle B, C, D (edges BC, CD, BD) is still a cycle; its costliest edge is BD{=}5, so remove it next. No cycle remains after that, leaving \{BC, AC, CD, DE\}, exactly 4 edges as Step 1 predicted, with total weight 1+2+3+6=12.

    Why: stopping only when both conditions hold, no cycle left and the right edge count reached, catches a cycle that Step 2 missed the first time.

Common mistakes

  • Removing an edge that lies on no cycle, which disconnects the graph instead of trimming it.
  • Removing the cheapest edge of a cycle instead of the costliest one.
  • Stopping after breaking one cycle without checking whether a second cycle remains.
  • Missing a cycle that only becomes visible once an earlier edge has already been chosen to stay.