What Is a Graph? Points and Connections, and Nothing Else

A graph consists of vertices, which are simply labelled points, and edges, each joining a pair of vertices. Nothing else is specified, so the same graph can be drawn in unlimited different ways, and two drawings that look completely unalike may represent the identical structure, since only the pattern of connections matters. Edges may be directed, meaning the connection runs one way, or undirected. They may carry weights representing cost, distance or capacity. The word is unfortunately shared with the plotted curves also called graphs, which are a different thing entirely, and the confusion is one of the more annoying collisions in mathematical vocabulary. Everything in the subject follows from questions about connection patterns, which turn out to be enormously rich for something defined so minimally.

A standard set of problems recurs across every application:

• •Shortest path between two vertices, which is what navigation software computes
• •Whether the structure is connected, and if not how it divides into separate pieces
• •Whether a route exists using every edge exactly once, which is the bridges problem that founded the subject
• •Whether a route exists visiting every vertex exactly once, which sounds similar and is computationally far harder
• •Colouring vertices so that no two connected ones share a colour, which models timetabling and frequency allocation
• •Finding the cheapest set of edges connecting everything, which is how networks are laid out economically

The subject is usually dated to a specific problem about a specific city. Königsberg had seven bridges connecting two islands and two banks, and the question was whether a walk existed crossing every bridge exactly once. Euler proved in 1736 that none did, and the important part was how he proved it, by discarding everything about the city except which land masses connected to which and how many bridges met at each, then showing that a solution requires a condition on those counts that the arrangement failed. That move, throwing away geometry and keeping only connectivity, defined the field. It also demonstrated something about proof, since the result establishes that no route exists rather than merely that none had been found, which is a different and stronger kind of answer.

A striking feature of the subject is that superficially similar questions have wildly different difficulty. Finding a route crossing every edge once is settled by checking a simple condition at each vertex and takes time proportional to the size of the graph. Finding a route visiting every vertex once has no such shortcut and is among the problems for which no efficient method is known, with the related question of the shortest such route being one of the standard examples of computational hardness. Colouring with two colours is easy to decide and colouring with three is hard. Finding the shortest path is efficient and finding the longest is not. That pattern, where a small change to the question moves it from routine to intractable, is one of the clearest illustrations available of what computational complexity is about, and graphs supply most of the standard examples.

The applications are so widespread that the subject has become basic infrastructure. Transport networks, utility grids and communication networks are graphs directly, and routing, capacity and resilience questions are graph problems. Social connections are graphs, and the study of their structure produced findings about clustering, about the small number of steps separating any two people and about how information and disease spread. Molecules are graphs of atoms and bonds, which is how chemical structures are stored and searched computationally. Dependencies between tasks form a graph whose properties determine scheduling. Web pages linked to each other form a graph whose structure was the basis of the ranking algorithm that made one search engine dominant. And neural connections, ecological food webs and citation patterns are all analysed with the same tools.

Points and connections with no position, distance or shape, so the same structure can be drawn in unlimited ways and only the pattern matters. Shortest paths, connectivity, colouring and cheapest spanning connections are the recurring questions. The field began when Euler discarded everything about a city except which land masses connected to which, and proved no route crossing every bridge once could exist.