What Is Graph Theory? Everything Reduced to Dots and Lines
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Strip away everything about a road map except which places connect to which, and what remains is a graph: a set of points and a set of links between them. That abstraction throws away distance, shape and position, and what survives turns out to answer questions about routes, schedules, circuits, molecules and social relations that the original detail obscured.
Where it started
The founding problem is a puzzle about a city. Konigsberg was built around a river with two islands and seven bridges, and residents asked whether a walk existed that crossed every bridge exactly once. Leonhard Euler showed in 1736 that it did not, and the important part is how he showed it. He observed that the geography was irrelevant: what mattered was only how many bridges met at each landmass. Each time a walk enters a landmass by one bridge it must leave by another, so every landmass except the start and the end needs an even number of bridges. In Konigsberg all four had an odd number, so no such walk exists. That argument discarded the map entirely and reasoned about connection alone, which is the move that created the subject, and the result generalises: a route crossing every edge exactly once exists precisely when the graph is connected and has zero or two points with an odd number of links.
The vocabulary
A small set of terms covers most applications, and each corresponds to something concrete:
- •Vertices and edges, meaning the points and the links, which might be cities and roads, people and friendships, or web pages and hyperlinks
- •Degree, the number of edges meeting a vertex, which measures how connected something is
- •Directed graphs, where edges point one way, which is what a one-way street system, a food web or a citation network requires
- •Weighted graphs, where edges carry a number representing distance, cost, capacity or time
- •Paths, cycles and connectivity, describing whether and how one vertex can be reached from another
- •Trees, connected graphs with no cycles, which describe hierarchies, file systems and the minimal network joining a set of points
- •Planar graphs, those drawable without edges crossing, which matters for circuit boards and for map colouring
The problems it solves
Several classic questions have efficient solutions and one famously does not. Finding the shortest route between two points in a weighted graph is solved by Dijkstra's algorithm, published in 1959, which is what every navigation system runs in some refined form. Finding the cheapest set of edges connecting everything, the minimum spanning tree, is solved by simple greedy algorithms and is used in network design. Determining the maximum flow through a network with capacity limits has efficient solutions and applies to pipelines, traffic and scheduling. Matching problems, pairing students to schools or doctors to hospitals, have algorithms guaranteeing a stable outcome, work that won a Nobel prize in economics. Against those sits the travelling salesman problem, finding the shortest route visiting every vertex once, which is computationally hard in the sense that no efficient general algorithm is known and finding one would resolve the largest open question in computer science, and which is therefore attacked with approximations that get close enough.
Where it turns up
The abstraction applies wherever relationships matter more than positions. Navigation and logistics route vehicles through weighted graphs. Timetabling and examination scheduling are graph colouring problems, assigning colours to vertices so that adjacent ones differ, where the colours are time slots and adjacency means a conflict. The four colour theorem, stating that any map can be coloured with four colours so no neighbouring regions match, is a graph result and was the first major theorem proved with essential computer assistance in 1976, which caused a genuine argument about what counts as a proof. Chemistry represents molecules as graphs of atoms and bonds, and the word graph in this sense entered use through chemical notation. Web search ranks pages by analysing the link graph. Epidemiology models transmission over contact networks. Social network analysis measures influence and community structure through the same tools, and neuroscience maps brain connectivity the same way.
The takeaway
A graph keeps only which things connect to which, discarding distance and position, and Euler founded the subject in 1736 by showing that the Konigsberg bridge walk was impossible using nothing but how many bridges met each landmass. Shortest paths, minimum spanning trees, maximum flow and stable matching all have efficient algorithms, while the travelling salesman problem does not. The same abstraction handles timetabling, molecules, web search, epidemics and brain connectivity.