What is a graph, really? — A tool for making relationships visible
From the bridges of Konigsberg to social networks, dependency management, and scheduling, an astonishing variety of problems reduce to graphs. This article explains the intuition behind undirected, directed, and weighted graphs, and why this abstraction is so powerful.
Open any graph theory textbook and you will find the declaration "" on the first page, stated with the calm assurance of self-evident truth. What the textbook rarely explains is why this abstraction is worth adopting. In this article, we will see that the concept of a graph – "a picture of relationships" – provides a unified language for a remarkably wide range of problems.
1 It all began with the bridges of Königsberg
In 1736, the mathematician Euler posed a deceptively simple question about the city of Kö
Euler's brilliant insight was that the shapes of the islands and riverbanks do not matter. All that matters is which landmasses are connected by which bridges– the connectivity relation alone.
By representing landmasses as points (vertices) and bridges as lines (edges), Euler created what we now call a graph.
2 Graphs are everywhere
The power of the graph abstraction lies in the sheer diversity of phenomena that reduce to the same formal structure.
graph TD
subgraph "Social network (undirected)"
U1["Alice"] --- U2["Bob"]
U2 --- U3["Carol"]
U1 --- U3
end
subgraph "Dependencies (directed)"
P1["React"] --> P2["react-dom"]
P1 --> P3["scheduler"]
P2 --> P3
end
style U1 fill:#f5f5f5,stroke:#333,color:#000
style U2 fill:#f5f5f5,stroke:#333,color:#000
style U3 fill:#f5f5f5,stroke:#333,color:#000
style P1 fill:#f5f5f5,stroke:#333,color:#000
style P2 fill:#f5f5f5,stroke:#333,color:#000
style P3 fill:#f5f5f5,stroke:#333,color:#0003 The formal definition – turning intuition into mathematics
To treat all of these examples within a single framework, we need precise definitions.
There is an important subtlety here. An edge in an undirected graph is a set, so ; but an arc in a directed graph is an ordered pair, so in general. Friendship is symmetric (undirected); dependency is not (directed). The mathematics captures this distinction exactly.
4 Why this abstraction is so powerful
5 Basic vocabulary – a shared language
Before proceeding further in graph theory, let us collect the essential terminology.
This follows from the simple observation that each edge contributes exactly one to the degree of each of its two endpoints. Simple as it is, the handshaking lemma is surprisingly powerful: it implies immediately, for instance, that the number of vertices of odd degree is always even.
6 Takeaway – graphs as an operating system for thought
A graph is not merely a picture of dots and lines. It is a universal language for reasoning about relationships. The fact that the bridges of Kö
In the next article, we turn to the question of how to walk through a graph. Why does BFS find shortest paths? The answer is a beautiful analogy with ripples on a pond.
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.