Graph Theory
“A graph is a map that throws away location and keeps only connection.”
The formula
G = (V, E), Σ(v∈V) deg(v) = 2|E|How to read it: a graph is a set of vertices V and a set of edges E joining them; summing every vertex's degree gives twice the number of edges
- V
- — the set of vertices—the 'dots'
- E
- — the set of edges—the 'lines' joining dots
- deg(v)
- — the degree of v—the number of edges attached to it
- Σdeg(v) = 2|E|
- — the degree sum equals twice the edge count (the handshake lemma)
The hook
Friendships, subway maps, the internet, molecules—all of them are captured by one simple picture: dots and lines.
In plain words
A graph is a collection of dots (vertices) and lines (edges) joining them. It records only what is connected to what, throwing away position, shape, and distance. It's a map of relationships stripped to the skeleton.
The intuition
Picture a subway map—the real distances and directions are wrong, but 'which station connects to which' is perfectly preserved. That's the spirit of a graph. Whatever the dots are (people, cities, web pages) and whatever the lines are (friendships, roads, links), looking only at the structure of connection makes very different problems become the same problem.
How it's built
Two parts—a vertex set V and an edge set E. Each vertex's 'degree' is the number of edges attached to it. The handshake lemma: adding up all the degrees gives exactly twice the number of edges (each edge is counted once at each of its two ends). This simple count is surprisingly powerful.
Example
A triangle graph: 3 vertices, 3 edges. Each vertex has degree 2, so the degree sum is 2+2+2 = 6 = 2 × 3 (the edge count). The handshake lemma holds exactly.
Common mistake
Here a 'graph' is not the curve of a function y=f(x). There are no axes and no curve—only a network of dots and the lines joining them. Same word, entirely different object.
Where it's used
Google's search ranking (PageRank), GPS shortest paths, social-network analysis, circuit design, scheduling and coloring problems, epidemic-spread models—every problem where things connect to things is a graph.
Where it came from
In 1736 Euler solved the puzzle of whether one could cross all seven bridges of Königsberg exactly once, opening the doors of graph theory and topology (the answer: impossible).
Prerequisites
Quick check
By the handshake lemma, what is the sum of all vertex degrees in a graph with 5 edges?
- 5
- 10✓
- 25
- 2.5
Practice
Find the sum of all vertex degrees in a graph with 4 edges.
Answer: 8
- handshake lemma: degree sum = 2 × number of edges
- = 2 × 4 = 8
Takeaway: Each edge adds 2 to the total degree.
Find the number of edges in the complete graph K₄ (4 vertices, every pair connected).
Answer: 6
- the number of ways to pick 2 of 4 vertices, C(4,2)
- = (4·3)/2 = 6
Takeaway: A complete graph Kₙ has n(n−1)/2 edges.
A graph has vertices of degree 3, 3, 2, 2. Find its number of edges.
Answer: 5
- degree sum = 3+3+2+2 = 10
- edges = 10 / 2 = 5
Takeaway: The edge count is half the degree sum.
Explain using degrees why no walk can cross each of Königsberg's seven bridges exactly once.
Answer: undefined
- such a walk (an Euler path) needs 0 or 2 vertices of odd degree
- in Königsberg all four landmasses have odd degree
- four odd-degree vertices (more than 2) makes it impossible
Takeaway: Three or more odd-degree vertices means no Euler path exists.