What a Graph Actually Is
A graph is a bunch of dots with lines between some of them. That is the entire definition. If that sounds too simple to deserve a whole branch of mathematics, hang on, because the interesting part is not the definition. It is how many completely unrelated problems turn out to be the same problem once you draw them this way.
The dots are called vertices (one is a vertex) or nodes. The lines are called edges. People use node and vertex interchangeably and nobody will correct you. I will say node from here on because it is shorter.
Why you already care about this
Every one of these is a graph, and once you notice that, the same handful of algorithms starts solving all of them:
| Situation | Nodes are | Edges are |
|---|---|---|
| Social network | people | friendships |
| Road map | intersections | streets |
| The web | pages | links |
| npm install | packages | dependencies |
| Git history | commits | parent relationships |
| Your circuit in the logic editor | gates and IO pins | wires |
That last row is not a stretch. A circuit really is a graph, which is why the same traversal code that finds your friends-of-friends can also work out which gates need re-evaluating when an input flips.
Have a look at one
Here are six graphs. They all use the same five dots in the same five places, and the only thing that changes is which lines are drawn and what those lines mean. Click through the tabs. Do not worry about understanding every label yet, the next lesson pulls each one apart properly.
Plain edges with no direction. If A connects to B, then B connects to A. Think friendships or roads that run both ways.
The words you need
Graph theory has a lot of vocabulary, and most tutorials dump all of it on you at once. You only need six words to start:
| Word | What it means |
|---|---|
| Neighbour | A node you can reach in one step |
| Degree | How many edges touch a node |
| Path | A sequence of nodes where each one connects to the next |
| Cycle | A path that ends where it started |
| Connected | Every node is reachable from every other node |
| Component | One connected island in a graph that has several |
Degree is worth a second look because it splits in two the moment edges have direction. A one-way street network gives every intersection an in-degree (roads arriving) and an out-degree (roads leaving), and those two numbers have no obligation to match. Flip the explorer above to the directed tab and the degree panel splits into two columns for exactly this reason.
Two numbers that show up everywhere
When you read about running times later, you will keep seeing V and E. V is the number of nodes, E the number of edges. An algorithm that runs in O(V + E) touches each node and each edge a constant number of times, which is about as good as it gets for anything that has to look at the whole graph.
The gap between those two numbers matters more than you would expect. A graph where every node connects to every other node has roughly V squared edges. A graph shaped like a tree has V minus 1. Same node count, wildly different edge count, and that difference decides which of the two representations in the next-but-one lesson you should reach for.
Next up: the different flavours of graph, and why an arrow on an edge changes so much about what you are allowed to conclude.