A subway map ignores real distances and shows only stations (dots) and the lines connecting them (edges) — that's all you need to plan a route. Graph theory models any network of connections this way, from friendships to the internet.
Dots and lines that model anything
A graph is a set of vertices (nodes) joined by edges. Graphs model road maps, social networks, and dependencies. The degree of a vertex is the number of edges touching it. A path is a walk that doesn't repeat vertices; a cycle is a path that returns to its start.
The sum of all vertex degrees equals twice the number of edges — because every edge adds one to the degree of each of its two endpoints.
- Draw a square with vertices A, B, C, D and edges AB, BC, CD, DA.
- Write the degree of each vertex.
- Add the degrees and divide by 2.
What you should see: Every vertex has degree 2, so the sum is 8, and 8 / 2 = 4 edges — exactly the four sides. That's the handshake lemma.