π¬ Scientist
Pure mathematics β no exam syllabus
Graph Theory β The Mathematics of Connections
Graph theory studies networks β collections of points (vertices) connected by lines (edges). It began with a simple question about bridges in KΓΆnigsberg and grew into one of the most applied branches of mathematics. Social networks, the internet, transportation, epidemiology, circuit design, and even the structure of molecules are all graphs. And at its frontier lies the most famous unsolved problem in computer science: P vs NP.
"Graph theory is the science of relationships. Everything is connected to everything else β graph theory makes that precise."
β Anonymous
Part 1
π Graphs β Vertices, Edges, and the Bridges of KΓΆnigsberg
The Birth of Graph Theory
How Seven Bridges Launched a Mathematical Revolution
In the 18th century, the city of KΓΆnigsberg had seven bridges crossing the Pregel River. The question: could you take a walk that crossed each bridge exactly once and return to your starting point? In 1736, Euler proved it was impossible β and in doing so, invented graph theory. He realized the problem wasn't about geography; it was about connections. The landmasses became vertices, the bridges became edges, and the answer depended only on the degrees of the vertices. A graph has an Eulerian circuit (a tour using every edge exactly once) iff every vertex has even degree. All seven KΓΆnigsberg bridges had odd degree β impossible.
Sometimes the deepest insights come from ignoring what something is and focusing only on how it's connected.
Basic Vocabulary
The sum of all vertex degrees equals twice the number of edges. Why? Each edge contributes 1 to the degree of each of its two endpoints, so it contributes 2 to the total sum.
Consequence: Every graph has an even number of vertices of odd degree. This is why Euler's seven bridges had an odd number of odd-degree vertices β making a Eulerian circuit impossible.
Paths, Cycles, and Connectedness
A path is a sequence of edges where no vertex repeats. A cycle is a closed path. A graph is connected if there's a path between every pair of vertices. A tree is a connected graph with no cycles β it has exactly nβ1 edges for n vertices. Trees are the minimal connected structures and appear everywhere: file systems, decision trees, family trees, spanning trees of networks.
Properties of Trees
A tree on n vertices has exactly nβ1 edges
Add one more edge β creates a cycle. Remove one edge β disconnects the graph.
Part 2
π¨ Graph Coloring β How Many Colors Do You Need?
The Four Color Theorem
A 124-Year Obsession That Changed Mathematics
In 1852, Francis Guthrie noticed that four colors sufficed to color any map of England so that adjacent counties had different colors. The question: is four always enough? The Four Color Theorem says yes β any planar graph (one that can be drawn without crossing edges) is 4-colorable. It was the first major theorem proven by computer (Appel and Haken, 1976), sparking controversy about what constitutes a proof. A graph's chromatic number Ο(G) is the fewest colors needed. For Kβ, Ο = n. For bipartite graphs, Ο = 2. For planar graphs, Ο β€ 4.
Sometimes a simple question takes over a century and a computer to answer.
Greedy Coloring Algorithm
Order the vertices. Give each vertex the smallest color not used by its already-colored neighbors. In the worst case, this uses at most Ξ+1 colors (where Ξ is the maximum degree). Brooks' theorem gives a tighter bound: for connected graphs that aren't complete or odd cycles, Ο(G) β€ Ξ.
Planar Graphs β Drawing Without Crossings
A graph is planar if it can be drawn in the plane with no edges crossing. Euler's formula for connected planar graphs:
Euler's Formula for Planar Graphs
V β E + F = 2
Vertices minus edges plus faces equals 2 (for connected planar graphs).
Consequences of Euler's Formula
For a planar graph with V β₯ 3: E β€ 3V β 6. This is why Kβ
(complete graph on 5 vertices) is non-planar β it has 10 edges, but 3Γ5β6 = 9, so it violates the bound. Kβ,β (utility graph) also violates a face-length bound and is non-planar. Kuratowski's theorem says a graph is planar iff it contains no subdivision of Kβ
or Kβ,β.
Part 3
β‘ Matchings and Flows β Connecting Pairs and Moving Stuff
Matchmaking Mathematics
Hall's Marriage Theorem and the Perfect Match
Suppose you have n jobs and n applicants, and each applicant is qualified for some subset of jobs. Can you assign each applicant a unique job they're qualified for? This is a matching problem on a bipartite graph. Hall's marriage theorem answers: a perfect matching exists iff for every subset of applicants, the set of jobs they collectively qualify for is at least as large. This simple condition appears in assignment problems, scheduling, and even online dating algorithms.
A graph doesn't need to be dense β it just needs enough connections for everyone to find a partner.
Maximum Matching
A matching is a set of edges with no shared vertices. A maximum matching contains as many edges as possible. The augmenting path algorithm finds one: start with any matching, find a path that alternates between unmatched and matched edges, flip the edges along the path to increase the matching size. Repeat until no augmenting path exists β then the matching is maximum.
In bipartite graphs, the size of a maximum matching equals the size of a minimum vertex cover (a set of vertices that touches every edge). This is KΓΆnig's theorem, and it's a special case of the max-flow min-cut theorem.
Example: In a graph with 4 jobs and 4 applicants, if the maximum matching has size 3, then there are 3 vertices that together touch every possible edge. Those 3 vertices form a bottleneck β explaining why 4 matches are impossible.
Network Flows β The Max-Flow Min-Cut Theorem
A flow network is a directed graph with a source (s), a sink (t), and capacities on edges. A flow sends as much "stuff" from s to t as possible without exceeding capacities. The max-flow min-cut theorem says the maximum flow equals the minimum capacity of a cut (a set of edges whose removal disconnects s from t). This is one of the most applied results in mathematics β it governs traffic flow, internet routing, airline scheduling, and the movement of goods in supply chains.
Max-Flow Min-Cut Theorem
Maximum flow = Minimum cut capacity
The bottleneck determines the throughput. The Ford-Fulkerson algorithm finds the max flow by repeatedly finding augmenting paths.
Part 4
π Deep Graph Theory β Ramsey, Random Graphs, and P vs NP
Order from Chaos
Ramsey Theory: Complete Disorder Is Impossible
In any group of 6 people, there must be either 3 mutual friends or 3 mutual strangers. This is R(3,3) = 6 β the smallest number where a monochromatic triangle is unavoidable. Ramsey theory says that in any large enough structure, patterns inevitably emerge. R(4,4) = 18, but R(5,5) is unknown β only that it's between 43 and 48. The Ramsey numbers grow extremely fast, and computing them is one of the hardest problems in combinatorics. The philosopher Wittgenstein famously tried to disprove R(3,3) = 6 by drawing a counterexample β and failed.
Complete randomness is impossible. Enough structure always contains order.
Extremal Graph Theory β TurΓ‘n's Theorem
What's the maximum number of edges in a graph on n vertices that contains no triangle? TurΓ‘n's theorem answers: the extremal graph is a complete bipartite graph with parts as equal as possible β βnΒ²/4β edges. More generally, if a graph has no Kα΅£ as a subgraph, the extremal number is given by the TurΓ‘n graph T(n, rβ1).
Mantel's Theorem (r=3)
A triangle-free graph on n vertices has at most βnΒ²/4β edges. Example: n = 6. Max edges without a triangle = 9 (a complete bipartite Kβ,β). If you add one more edge, a triangle appears. This is the simplest case of TurΓ‘n's theorem.
Random Graphs β The ErdΕsβRΓ©nyi Model
In the G(n,p) model, each of the n(nβ1)/2 possible edges appears independently with probability p. This seems random, but it produces remarkably predictable behavior. At p = 1/n, the graph undergoes a phase transition: below this threshold, components are tiny (O(log n)); above it, a giant component emerges containing a constant fraction of vertices. This models how epidemics spread, how social networks form, and how the internet connected β suddenly, not gradually.
ErdΕsβRΓ©nyi Phase Transition
At p = 1/n, a giant component suddenly appears
Below: isolated trees. Above: a single component containing most vertices. This critical point is remarkably sharp.
Graph Algorithms β P vs NP
Many graph problems have efficient (polynomial-time) algorithms: finding shortest paths (Dijkstra), minimum spanning trees (Kruskal), maximum matchings, network flows. These are in P. But others seem to require checking all possibilities: finding a Hamiltonian cycle (a tour visiting each vertex once), the traveling salesman problem, graph coloring with 3 colors, finding a clique of a given size. These are in NP β solutions can be checked quickly, but finding them seems hard. The P vs NP question asks whether these are truly distinct: can every problem whose solution is easy to verify also be solved quickly? A $1M Clay Millennium problem, and arguably the most important open question in computer science.
"Graph theory is the ultimate applied mathematics β it doesn't matter whether you're studying molecules or social networks, it's all graphs underneath."
β Paul ErdΕs
π― Practice β Check Your Graph Intuition
These puzzles build graph theory intuition β no code needed.