In 1736, Leonhard Euler proposed a solution to a puzzle about bridges in a Prussian city. In doing so, he accidentally founded one of the most widely applied branches of mathematics: graph theory.
Why does graph theory matter? #
In computing and mathematics, modeling relationships between objects shows up everywhere:
- Computer networks: packet routing and failure analysis depend on graph algorithms, and distance and connectivity are the subject of Paths, Cycles, and Connectivity
- Search engines: Google’s PageRank ranks pages by computing centrality in a graph of the web, and the calculation appears step by step in Graphs: A Language for Modeling Connections
- Navigation: map and GPS (Global Positioning System) navigation apps compute shortest paths with accelerated variants of Dijkstra’s algorithm (breadth-first search solves the unweighted case), both presented in Paths, Cycles, and Connectivity
- Social networks: analyzing communities, influencers, and the spread of information are graph problems. Zachary’s Karate Club, a real network that split in two, appears in Degree of a Vertex and in Paths, Cycles, and Connectivity
- Compilers and dependencies: analyzing modules and detecting cycles in software projects use directed graphs. Dependency cycles appear in Paths, Cycles, and Connectivity, and topological sorting, in Directed Graphs
- Bioinformatics: genome assembly and protein interaction networks are modeled as graphs. Genome assembly by Eulerian trails appears in Eulerian and Hamiltonian Graphs
Graph theory provides the language and the algorithms to handle these problems with mathematical rigor.
This series covers the foundations of graph theory in a systematic and accessible way, starting from the basic definitions and advancing to results such as Euler’s Theorem and Kuratowski’s Theorem.
What You Will Learn #
Over the 9 articles in this series, we will build the foundation of graph theory:
Graphs: A Language for Modeling Connections #
The story of the Bridges of Königsberg problem, the fundamental idea behind graphs, and why this abstraction serves so many problems. We will see how the same mathematical language models computer networks, chemical molecules, social networks, and much more.
→ Graphs: A Language for Modeling Connections
Definitions and Notation in Graph Theory #
The formal language: simple graph \(G = (V, E)\), neighborhood, isolated and universal vertex, complement of a graph, subgraphs (induced and spanning), complete graphs \(K_n\), null graphs \(N_n\), cliques, and independent sets.
→ Definitions and Notation in Graph Theory
Degree of a Vertex and the Handshaking Lemma #
The degree \(d(v)\) of a vertex, minimum degree \(\delta(G)\) and maximum degree \(\Delta(G)\), regular graphs, and the Handshaking Theorem: \(\sum d(v) = 2|E|\). Corollaries about parity and degree sequences.
→ Degree of a Vertex and the Handshaking Lemma
Isomorphism and Matrix Representation #
When are two graphs structurally identical? The definition of isomorphism, necessary conditions for checking it, and how to represent graphs computationally: adjacency matrix and incidence matrix.
→ Isomorphism and Matrix Representation
Paths, Cycles, and Connectivity #
How to navigate a graph: the distinctions between walk, trail, path, and cycle. Connectivity, connected components, distance, diameter, center, and how to compute distances with breadth-first search and Dijkstra’s algorithm. Bipartite graphs and their characterization by odd cycles.
→ Paths, Cycles, and Connectivity
Trees: The Most Elegant Structure in Graphs #
Trees as connected acyclic graphs. The fundamental theorem \(m = n-1\), uniqueness of paths, leaves, center (1 or 2 vertices), spanning trees, and the ubiquity of rooted trees in computing.
→ Trees: The Most Elegant Structure in Graphs
Eulerian and Hamiltonian Graphs #
Special tours: the Eulerian circuit traverses every edge, the Hamiltonian cycle visits every vertex. Euler’s Theorem, the Dirac and Ore theorems for Hamiltonicity, and the famous Traveling Salesman Problem.
→ Eulerian and Hamiltonian Graphs
Planar Graphs: When Crossing Is Unavoidable #
When is it possible to draw a graph without crossing edges? Euler’s Formula \(n - m + f = 2\), corollaries proving that \(K_5\) and \(K_{3,3}\) are not planar, graph subdivisions, Kuratowski’s Theorem, and the coloring of planar graphs, with the Four Color Theorem.
→ Planar Graphs: When Crossing Is Unavoidable
Directed Graphs: When Direction Matters #
Digraphs to model asymmetric relationships. In-degree and out-degree, sources and sinks, strong/unilateral/weak connectivity, nonsymmetric adjacency matrices, and applications in networks and dependency analysis, using DAGs (Directed Acyclic Graphs) and topological sorting.
→ Directed Graphs: When Direction Matters
The articles were designed to be read in order, and the diagram below shows why. Besides the sequence, the dashed arrows mark results from one article that come back as a tool in a later article:
flowchart TD
A1["Graphs: a language
for modeling connections"] --> A2["Definitions
and notation"]
A2 --> A3["Degree and the
Handshaking Lemma"]
A3 --> A4["Isomorphism
and matrices"]
A4 --> A5["Paths, cycles
and connectivity"]
A5 --> A6["Trees"]
A6 --> A7["Eulerian and
Hamiltonian"]
A7 --> A8["Planar graphs"]
A8 --> A9["Directed graphs"]
A3 -.->|"Handshaking
in Christofides"| A7
A5 -.->|"bipartite:
K3,3 has no triangles"| A8
A6 -.->|"spanning tree
in Euler's Formula"| A8
A3 -.->|"in-degree
and out-degree"| A9
Who Is This Series For? #
This series was written for those who are familiar with basic mathematics (high school level) and want to understand the mathematical foundations that underpin computer science and network analysis.
No programming experience is needed. The concepts are presented with concrete examples, worked exercises, and connections to real applications.
Prerequisites #
The concepts in this series connect naturally with other discrete mathematics topics covered here on the site:
- Set theory: the language of sets is everywhere. See the series The Language of Sets
- Combinatorics: counting paths, cycles, and structures in graphs. See the series The Art of Counting
- Mathematical induction: used in the proofs of the fundamental theorems. See the series From Base Case to Infinity
If you are not yet familiar with these topics, you can follow the other series before studying graph theory.
What Comes Before and After #
This series is part of a larger sequence on Discrete Mathematics:
- Before: The Language of Sets, From Base Case to Infinity, and The Art of Counting, which cover sets, mathematical induction, and combinatorics
- Now: graph theory, with connections, structure, and algorithms
Each series can be read independently, but the progression was planned to build intuition gradually.
Quick Reference Table #
The topics and main results of each article in this series:
| Article | Topic | Main result / concept |
|---|---|---|
| 1 | Graphs: A Language | Modeling relationships as graphs |
| 2 | Definitions and Notation | \(G = (V, E)\), cliques, subgraphs |
| 3 | Degree and Handshaking | \(\sum d(v) = 2\lvert E \rvert\) |
| 4 | Isomorphism and Matrices | Adjacency matrix, isomorphism |
| 5 | Paths and Connectivity | Connected components, distance, breadth-first search, bipartite graphs |
| 6 | Trees | \(m = n - 1\), spanning trees |
| 7 | Eulerian and Hamiltonian | Euler’s Theorem, Dirac’s Theorem |
| 8 | Planar Graphs | \(n - m + f = 2\), Kuratowski’s Theorem, Four Color Theorem |
| 9 | Directed Graphs | Digraphs, DAGs, strong connectivity |
Ready to start? Let’s begin where it all started: the Bridges of Königsberg.
Enjoy the reading!
