Graph theory studies networks of objects (vertices) connected by links (edges). Born in 1736 from a single recreational puzzle solved by Euler, it has grown into an essential tool across computer science, biology, logistics, and social science — anywhere relationships between discrete objects need to be modelled and analysed.
A graph (in this mathematical sense, not a chart of numbers) is simply a collection of dots, called vertices, connected by lines, called edges. That's it — an almost absurdly simple idea that turns out to be one of the most useful tools in all of mathematics.
In the city of Königsberg (now Kaliningrad), seven bridges connected four landmasses across a river. Citizens wondered: could you walk through the city crossing every bridge exactly once, and return to your starting point? In 1736, Leonhard Euler proved it was impossible — and in doing so, invented an entirely new branch of mathematics. His trick: he realised the exact shapes and distances didn't matter — only which landmasses were connected to which. This is exactly the abstraction that defines a graph.
A graph G = (V, E) consists of a set of vertices V and a set of edges E, where each edge connects two vertices. In an undirected graph, edges have no direction (friendship is mutual). In a directed graph (digraph), edges point one way (a one-way street, a Twitter "follow").
Euler proved: a walk crossing every edge exactly once (now called an Eulerian path) exists if and only if the graph has exactly 0 or 2 vertices of odd degree. The Königsberg graph has 4 vertices, all of odd degree — so no such walk is possible. This single insight founded graph theory as a field.
In any graph, the sum of all vertex degrees equals twice the number of edges (since each edge contributes to the degree count of exactly two vertices). A direct consequence: the number of vertices with odd degree must always be even.
Assigning colours to vertices so that no two connected vertices share a colour is graph colouring. The minimum number of colours needed is the chromatic number. This is the abstract structure behind the Four Colour Theorem — map colouring is exactly graph colouring on planar graphs.
Dijkstra's algorithm (1956) finds the shortest path between vertices in a weighted graph (where each edge has an associated cost or distance) in polynomial time, provided all weights are non-negative. This algorithm underlies most real-world route-finding software, from GPS navigation to network packet routing.
A spanning tree of a connected graph is a subgraph that includes every vertex and forms a tree (connected, no cycles) using the minimum possible number of edges. A minimum spanning tree (found efficiently by Kruskal's or Prim's algorithms) finds the cheapest way to connect all vertices when edges have costs — directly applicable to network design problems like laying cable or pipeline infrastructure at minimum cost.
Many real-world networks (the internet, citation networks, social networks) exhibit a "scale-free" structure, where vertex degree follows a power-law distribution — a small number of highly-connected "hub" vertices and many low-degree vertices. Barabási and Albert (1999) proposed a preferential-attachment model explaining how such networks emerge naturally from simple growth rules ("rich get richer" connectivity), a discovery that significantly influenced modern network science across disciplines.
The Travelling Salesman Problem (find the shortest route visiting every vertex exactly once and returning to the start) is deceptively simple to state but belongs to the NP-complete complexity class — believed (though not proven) to have no efficient general algorithm. This makes it a benchmark problem in computational complexity theory, directly connected to the P vs NP question, one of the seven Millennium Prize Problems.
As discussed in the Four Colour Theorem entry, the map-colouring problem is precisely the question of chromatic number for planar graphs — a striking example of how graph theory provides the right abstraction for translating an intuitive geometric question (map colouring) into precise combinatorial language, ultimately resolved computationally in 1976.