Graph theory runs GPS, social networks and Sudoku. Here's the math behind all three.

Every time you open Google Maps, scroll through Instagram or get a friend recommendation on LinkedIn - the same piece of math runs underneath. Not similar math. The exact same idea.

It's called graph theory. It's 200 years old. Most people have never heard of it. And once you see it you'll never look at a navigation app, a social network or even a Sudoku puzzle the same way again.

Here's what it is, why it matters and how it runs more of your daily life than you think.

What a graph actually is

Forget the bar charts and pie charts. In computer science a graph means something completely different.

A graph is a network of connections. Two components - nodes and edges. That's it.

Nodes   |  the things
Edges   |  the connections between them

In a city map:

Nodes   |  intersections
Edges   |  roads between intersections

In a social network:

Nodes   |  people
Edges   |  friendships between them

In a recommendation system:

Nodes   |  users and products
Edges   |  who bought what

The same structure. Different labels. Same math underneath.

This is why graph theory is powerful. You learn one framework and it solves problems in navigation, social media, biology, circuit design and dozens of other fields that look completely unrelated on the surface.

Why GPS is a graph problem

When you type a destination into Google Maps the app does one thing: finds the shortest path between two nodes in a graph.

Your location     =  starting node
Destination       =  ending node
Roads             =  edges
Traffic/distance  =  edge weights

The algorithm reads the graph, calculates the cost of every possible route and returns the cheapest one. This is called the shortest path problem and it's one of the most studied problems in all of computer science.

The reason weighted graphs matter here: not all edges are equal.

Unweighted graph:

Every road is the same
Shortest path = fewest roads

Weighted graph:

Roads have different costs
Highway vs side street
Clear road vs traffic jam
Shortest path = lowest total cost

You          →  connected to A, B, C, D
A            →  connected to you, E, F
B            →  connected to you, F, G
C            →  connected to you, H
D            →  connected to you, I, J

Google Maps uses weighted graphs where the weights change in real time based on traffic data. The graph updates constantly. The algorithm recalculates constantly. Every route you've ever followed was the output of finding the shortest path through a weighted graph with hundreds of millions of nodes.

Why Facebook friend recommendations are a graph problem

You have four friends on a platform. The platform wants to recommend new people you might know.

The graph already contains all the information needed:

The recommendation algorithm does one thing: finds nodes that are close to you in the graph but not yet connected to you directly.

Friends of friends:

A's friends  →  E, F
B's friends  →  F, G
C's friends  →  H
D's friends  →  I, J

F gets recommended first because two of your existing friends are already connected to F. The more mutual connections two nodes share the shorter the path between them in the graph and the stronger the recommendation signal.

This is why every "people you may know" feature on every platform works the same way. They're all traversing the same graph structure and counting shared connections.

Why Sudoku is a graph problem

This one surprises people. A puzzle that looks like pure logic turns out to be a specific graph theory problem called graph coloring.

Here's how computers see Sudoku:

Assign each number 1-9 a color
Each cell in the grid = a node
Constraint: no two neighboring cells can have the same color

Connect the nodes:

All cells in the same 3x3 grid  →  connected to each other
All cells in the same row       →  connected to each other
All cells in the same column    →  connected to each other

Now the puzzle becomes: given this graph and these colors, assign one color to each node so that no two connected nodes share the same color.

This is the graph coloring problem. It has well-known algorithms. Computers solve it efficiently. Sudoku goes from "logic puzzle" to "graph traversal" and the solution follows automatically from the structure.

Sudoku constraint    =  no repeated numbers in row/column/box
Graph constraint     =  no two connected nodes share a color
Same problem         =  same algorithm
Different label      =  identical math

The two algorithms that power all of this

Every graph application - GPS, social networks, Sudoku - uses some version of two fundamental algorithms for moving through a graph.

Depth First Search - DFS

Think of this as the bold explorer approach. You pick a starting node, go as deep as possible down one path until you hit a dead end, then backtrack and try another path.

Start at node 0
↓
Go to node 1
↓
Go to node 2
↓
Dead end - backtrack to node 1
↓
Go to node 3
↓
Continue until every node visited

DFS answers questions like: is there a path between these two nodes at all? Does this graph have cycles? What are all the connected components?

Applications: cycle detection, maze generation, topological sorting, finding connected components.

Breadth First Search - BFS

Think of this as the methodical approach. You visit all nodes at distance 1 from the start, then all nodes at distance 2, then distance 3. Layer by layer outward like ripples in water.

Start at node 0
↓
Visit all neighbors of node 0  (distance 1)
↓
Visit all their neighbors      (distance 2)
↓
Continue until every node visited

BFS guarantees something DFS doesn't: the first time it reaches a node it has found the shortest path to that node. This is why BFS powers GPS and shortest path problems.

Applications: shortest path, social network friend recommendations, GPS navigation, the bucket fill tool in MS Paint.

DFS   |  explores as deep as possible first
      |  good for: existence of paths, cycles, components

BFS   |  explores all nearby nodes first
      |  good for: shortest paths, distance calculations

The bucket tool in MS Paint is BFS

This is the one that surprises people most. The fill bucket in any paint application - click a region and watch it fill with color - is breadth first search applied to an image grid.

The algorithm sees the image as a graph:

Each pixel   =  node
Adjacent pixels (up/down/left/right)  =  edges
Same color pixels  =  connected component
When you click:
Starting pixel identified
↓
BFS spreads outward to all connected pixels with same color
↓
Each pixel visited gets filled with new color
↓
Stops when it hits pixels with different color

he "flood fill" problem is BFS on a pixel graph. The same algorithm that finds the shortest route in Google Maps fills a region in a drawing app. Same math. Different labels.

Types of graphs and why they matter

Not all graphs are equal. The type of graph you use changes what problems you can solve.

Undirected graph   |  edges go both ways
                   |  A connected to B = B connected to A
                   |  used for: friendships, roads

Directed graph     |  edges go one way
                   |  A → B does not mean B → A
                   |  used for: web links, task dependencies

Weighted graph     |  edges have costs
                   |  used for: GPS, traffic, distances

Tree               |  connected graph with no cycles
                   |  removing any edge disconnects it
                   |  used for: file systems, HTML structure

Twitter follows are a directed graph - you can follow someone who doesn't follow you back. Facebook friendships are an undirected graph - friendship goes both ways. Google Maps is a weighted directed graph - some roads are one-way and every road has a cost.

The same underlying theory applies to all of them.

The problem nobody has solved

Graph theory has efficient algorithms for almost everything covered above. Shortest path - solved. Connected components - solved. Graph coloring - solved for practical cases.

But one problem has no efficient solution and likely never will.

The Hamiltonian path problem: does a path exist that visits every node in a graph exactly once?

Euler path (visits every EDGE once) → efficient algorithm exists
Hamiltonian path (visits every NODE once) → no efficient algorithm known

These two problems look almost identical. One is solved. One is not. Every algorithm anyone has found for Hamiltonian path runs in exponential time - meaning it gets catastrophically slower as the graph gets bigger.

If you find an efficient algorithm for this problem you would resolve one of the most famous open questions in computer science and mathematics. The Clay Mathematics Institute would give you $1,000,000. Every major award in computer science would follow.

Most researchers believe no efficient algorithm exists. But nobody has proven it. This open question - whether some problems are fundamentally harder than others - is called P versus NP and it's been unsolved since 1971.

Why graph theory matters more in the AI era

Graph theory was already powerful. In the AI era it became foundational.

Every knowledge graph that makes AI systems smarter is graph theory. Every recommendation algorithm that decides what you see next is graph traversal. Every coding agent that understands dependencies between files is reading a dependency graph. GraphRAG - the system that gives AI 18% better accuracy and 85% lower costs - is graph theory applied to retrieval.

Knowledge graphs    |  facts stored as nodes and edges
Recommendation AI   |  graph traversal on user behavior
Coding agents       |  dependency graphs of codebases
GraphRAG            |  graph theory applied to AI retrieval

The AI systems that understand architecture rather than just files, that find causal chains rather than just text fragments, that remember relationships between facts rather than just words - all of them run on the same 200-year-old framework.

Nodes. Edges. Traversal. That's graph theory. That's GPS. That's social networks. That's Sudoku. That's the AI system that just fixed a production bug by tracing the dependency chain your regular search would never have found.

Most people will keep using these systems without understanding what runs underneath. A few will see the graph in everything and start building on top of it.

/ If this was useful - follow