Network Design

Graph Theory · Axiom Academy

How graph theory saves billions in infrastructure costs Imagine you're hired to connect 6 cities with fiber optic cables for a new telecommunications network. Each possible connection has a different cost based on distance and terrain. Your goal: Connect all cities so they can communicate, while minimizing the total cable cost. The numbers on each line represent the cost in millions of dollars. Try building the network yourself! Click the button below to see different possible solutions. Some use fewer cables, others use more redundant connections. What pattern did you notice about the optimal solution? The minimum cost network that connects all 6 cities uses exactly how many cables? The Mathematics: Minimum Spanning Trees What you discovered is a fundamental concept in graph theory called a Minimum Spanning Tree (MST) . A tree with n vertices always has exactly n - 1 edges For our 6 cities, we need exactly 6 - 1 = 5 cables to create a connected network with no cycles. This is the minimum number needed to connect everything. Connected: Every city can reach every other city Acyclic: No redundant loops (which would waste money) Minimum: Uses the cheapest possible edges to achieve connection Minimum spanning trees aren't just theoretical—they solve real infrastructure problems worth billions of dollars: Connect power plants to neighborhoods Minimize transmission line costs Reduce energy loss over distance Example: Texas power grid uses MST algorithms

This is the written version of the interactive lesson above. See the full Graph Theory course.