Graph theory

Dots and lines between them: that is all a graph is. Yet the same picture describes a road map, a network of friends, a molecule and the internet, and the questions you can ask about it, from the number of colours it needs to whether you can trace it in one stroke, have kept mathematicians busy since 1736.

A graph of ten vertices, the Petersen graph, with its vertices coloured in three colours so that no edge joins two of the same colour
A graph of ten vertices, the Petersen graph, with its vertices coloured in three colours so that no edge joins two of the same colour

Vertices and edges

A graph has vertices, also called nodes, and edges, each joining two vertices. Where the vertices are drawn does not matter, only which pairs are joined, so the same graph can look very different on paper. The graphs in the playground are simple: no edge from a vertex to itself, and at most one edge between two vertices. With n vertices there can be at most n(n − 1) / 2 edges; a graph that has them all is called complete, and K5 is the complete graph on five vertices.

Degrees and the handshake lemma

The degree of a vertex is the number of edges at it. Add up all the degrees and you get exactly twice the number of edges, because every edge has two ends and is counted once at each. This is the handshake lemma: in any group, the handshakes counted person by person add up to twice the number of handshakes. It also means that the number of vertices with an odd degree is always even. A graph in which every vertex has the same degree k is called k-regular.

Connected graphs, trees and cycles

A graph is connected when you can get from every vertex to every other along the edges; otherwise it falls apart into pieces, called components. A cycle is a round trip that comes back to its start without using a vertex twice, and the length of the shortest one is the girth. A connected graph without a cycle is a tree, and a tree with n vertices always has exactly n − 1 edges: one fewer and it falls apart, one more and it has a cycle. Every connected graph contains a spanning tree, a tree that reaches every vertex using only some of the edges.

Bipartite graphs and colouring

Colour the vertices so that no edge joins two vertices of the same colour. The fewest colours that do it is the chromatic number. One colour is enough only without edges. Two colours are enough exactly when the graph is bipartite: its vertices split into two sides and every edge goes across. Dénes Kőnig showed in 1936 that this is the same as having no cycle of odd length, because an odd cycle cannot alternate between two colours. For three or more colours no such simple test is known: deciding whether three colours are enough is NP-complete, so programs search, as the playground does.

An example: the Petersen graph

Take a pentagon A–B–C–D–E and a five-pointed star F–H–J–G–I inside it, and join each corner of the pentagon to a point of the star: A–F, B–G, C–H, D–I and E–J. That is the Petersen graph, with 10 vertices and 15 edges. Every vertex has degree 3, so the degrees add up to 30, twice 15. Its shortest cycle has length 5, so it has no triangle, but the pentagon is an odd cycle, so it is not bipartite and needs 3 colours. Any two vertices are at most 2 edges apart, so its diameter is 2. All ten degrees are odd, so it has no Euler trail, and it cannot be drawn without crossings.

Euler paths and the bridges of Königsberg

The city of Königsberg had seven bridges joining four pieces of land, and people asked whether you could walk across each bridge exactly once. In 1736 Leonhard Euler showed you could not, and graph theory began. Each time a walk passes through a piece of land it uses two bridges, so only the start and the end may have an odd number of them, and all four pieces of Königsberg had an odd number. A trail that uses every edge once is now called an Euler path, or an Euler circuit when it ends where it started. Carl Hierholzer proved in 1873 that the condition is also enough: if all edges are in one piece and at most two degrees are odd, the trail exists, and his method of joining up round trips still finds it.

A historical bird’s-eye map of Königsberg (Koningsberga), showing the Pregel river and the island at the heart of the seven-bridges problem. In 1736 Leonhard Euler showed that no walk could cross each bridge exactly once, and graph theory began.
A historical bird’s-eye map of Königsberg (Koningsberga), showing the Pregel river and the island at the heart of the seven-bridges problem. In 1736 Leonhard Euler showed that no walk could cross each bridge exactly once, and graph theory began.
Portrait of Leonhard Euler
Portrait of Leonhard Euler

Distance, diameter and the complement

The distance between two vertices is the fewest edges on a path between them, and the diameter is the largest distance in the graph; in a graph that is not connected it is infinite. Social networks have small diameters, the idea behind six degrees of separation. The complement of a graph has the same vertices and joins exactly the pairs that were not joined. Of a graph and its complement, at least one is always connected.

Explore it

The playground opens with the Petersen graph coloured in three colours. Click Degrees and check the handshake lemma, click Bipartite to see an odd cycle, then load the cube and see the two sides appear. Load the house and click Euler trail to see where the one stroke has to start. Draw your own graph and add an edge at a time: watch the shortest cycle shrink, the diameter drop, and the chromatic number go up when the last edge of a K4 goes in.

Frequently asked questions

What is the difference between a path, a trail and a walk?

A walk is any sequence of vertices joined by edges, and may repeat both. A trail may repeat vertices but not edges, which is why an Euler trail can pass through a vertex several times. A path repeats neither.

What is the four colour theorem?

It says that every graph you can draw on paper without crossing edges can be coloured with at most four colours, so any map needs no more than four. It was proved in 1976 by Kenneth Appel and Wolfgang Haken with the help of a computer, the first major theorem proved that way.

What is a Hamiltonian cycle?

A cycle that visits every vertex exactly once, instead of every edge. It looks like the Euler question, but no simple test for it is known: deciding whether a graph has one is NP-complete. The Petersen graph has a Hamiltonian path but no Hamiltonian cycle.

Where is graph theory used?

Route planners search road graphs, search engines rank web pages by their links, compilers colour graphs to share processor registers, timetables avoid clashes by colouring a graph of conflicts, chemists count molecules as graphs, and networks of computers, power lines and friends are studied as graphs.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the Graph Theory Playground