Trees

Connected, with no loops

An interactive lesson with 8 steps, about 7 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• A tree is connected with no cycles. With n vertices it has n − 1 edges.
• Removing an edge from a tree disconnects it. Adding one creates a cycle.
• A minimal network connecting n points always has n − 1 links.

Steps

1. Connect the towns
2. Trees
3. Is it a tree?
4. The cheapest network
5. Kruskal’s algorithm
6. Kruskal at work
7. How many trees?
8. Knockout tournament