Graph theory: foundations, history and representation
By Brenner Cruvinel • 7 minutes read
Excerpt adapted from Wikipedia, kept here so I have it properly archived. It is curation, not original content.
I think in graphs in a world that makes me speak in sequence. In 2016 I saved this excerpt from Wikipedia to have the fundamentals at hand. It is curation, not my own text: the source and the licence are at the end.
Definition
Graph theory is the branch of mathematics that studies the relationships between the objects of a set. It uses structures called graphs, $G(V, E)$, where $V$ is a non-empty set of objects called vertices (or nodes) and $E$ (edges) is a subset of unordered pairs of $V$.
Depending on the application, edges may or may not have a direction, an edge may or may not be allowed to connect a vertex to itself, and vertices and edges may have a numerical weight attached. If an edge has a direction, shown by an arrow, we have a digraph, or directed graph. A graph with a single vertex and no edges is the trivial graph.
Structures that can be represented as graphs are everywhere. Wikipedia's link structure, for example, is a digraph: the vertices are the articles, and there is an edge from A to B if and only if A contains a link to B. Digraphs also represent finite state machines.
History
Leonhard Euler's paper on the problem of the seven bridges of Königsberg, from 1736, is considered the first result in graph theory. It is also one of the first topological results in geometry, because it does not depend on measurement, which shows the deep connection between graphs and topology.
More than a century later, while Listing was introducing the concept of topology, Cayley studied a particular class of graphs, trees, out of interest in analytical forms in differential calculus, with implications for theoretical chemistry. The first textbook on graph theory was written by Dénes König and published in 1936.
The four colour problem asks whether any map drawn on a plane can have its regions coloured with four colours so that no two regions sharing a border get the same colour. Francis Guthrie formulated the question in 1852, and the first written record is a letter from that year by Augustus De Morgan to William Rowan Hamilton. The proof only came in 1976, from Appel and Haken, and it was one of the first major proofs done with the help of a computer.
Basic definitions
A directed graph (digraph, or quiver) consists of a non-empty set $V$ of vertices, a set $E$ of edges and maps $s, t : E \to V$, where $s(e)$ is the source and $t(e)$ is the target of the directed edge $e$.
An undirected graph is given by $V$, $E$ and a function $w : E \to P(V)$ that assigns to each edge a subset of two (or one) elements of $V$, its endpoints.
In a weighted graph, an additional function $E \to \mathbb{R}$ assigns a cost to each edge. This kind of graph shows up in optimal route problems, like the travelling salesman.
Example graph: $V = {1, 2, 3, 4, 5, 6}$ and $E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}}$. The drawing should not be confused with the graph itself, which is the abstract structure. What matters is which vertex is connected to which, and by how many edges.
Storing graphs in a computer
There are two families of structure, with the classic trade-off between memory and access speed.
List structures, good for sparse graphs and light on memory: the adjacency list associates each vertex with the list of vertices it shares an edge with, and the incidence list stores the edges incident to each vertex.
Matrix structures, with fast access and more memory: the incidence matrix holds zeros and ones, with one row per vertex and one column per edge, and the adjacency matrix has vertices on both rows and columns, with 1 marking adjacency. In computing, a finite graph with $n$ vertices is usually represented by the $n \times n$ adjacency matrix, whose value at row $i$, column $j$, gives the number of edges from the $i$-th to the $j$-th vertex.
Concepts
The valency, or degree, of a vertex is the number of edges incident to it, with a loop counting twice. The handshaking lemma says that the sum of the degrees of all vertices is twice the number of edges:
$$2m = \sum_{v \in V} \deg(v)$$
In a digraph, out-degree and in-degree are distinguished.
A walk between A and B is an alternating list of vertices and edges, and its length is the number of edges, counting repetitions. A path is a sequence of vertices in which each one has an edge to the next. In a simple path, no vertex repeats.
- An Eulerian path uses each edge exactly once, and an Eulerian cycle does that and closes. Deciding whether one exists is easy: you only need to look at the vertex degrees
- A Hamiltonian path visits each vertex exactly once, and a Hamiltonian cycle does that and closes. Deciding whether one exists is NP-complete
A cycle, or circuit, is a path that starts and ends at the same vertex. A cycle of length 1 is a loop. A graph is acyclic if it contains no simple cycle.
Types of graph
| Type | Definition |
|---|---|
| Simple | Undirected, no loops, at most one edge between two vertices |
| Multigraph | Allows several edges between the same vertices |
| Pseudograph | Contains parallel edges and loops |
| Complete | Every vertex connects to all others; $K_n$ has $n(n-1)/2$ edges |
| Null | Empty set of vertices |
| Empty | Empty set of edges |
| Regular | All vertices have the same degree |
| Connected | There is a path from any vertex to any other; it is $k$-connected if this holds after removing $k-1$ vertices |
| Tree | Simple, acyclic and connected graph; sometimes one vertex is the root |
| Forest | A set of trees, acyclic |
| Planar | Can be drawn on the plane without crossing edges; $K_n$ with $n > 4$ is not planar |
| Bipartite | Vertices in two sets, with no edge inside the same set; it is bipartite if and only if it contains no odd-length cycle |
Beyond these: subgraph, spanning subgraph, induced subgraph and partial graph; articulation point (a vertex whose removal disconnects the graph) and bridge (an edge with the same effect); clique (a subgraph that is also complete); independent set (vertices not adjacent to each other); complete bipartite graph and $k$-partite graph ($k$-colouring); and the four colour theorem, which says every planar graph can be coloured with four colours.
Traversal and algorithms
Traversing a graph means systematically visiting all vertices and all edges. The two basic methods:
- BFS uses a queue. It visits nodes starting from the shallowest level and computes the shortest distance, in number of edges, to all reachable vertices. The subgraph of those paths is the breadth-first tree
- DFS uses a stack. It expands the first child and goes deeper until it finds the target or a leaf, then backtracks. On wide graphs, it usually uses less memory than BFS
The running time of both is proportional to the number of vertices plus the number of edges.
Problems and algorithms around this: graph colouring, the four colour theorem, independent set, clique, shortest path, minimum spanning tree, the seven bridges of Königsberg, route inspection (Chinese postman), travelling salesman, maximum flow (Ford-Fulkerson), Dijkstra, Kruskal, nearest neighbour and Prim.
Generalization
In a hypergraph, an edge can connect more than two vertices. An undirected graph can be seen as a simplicial complex, with simplices of dimension one (the edges) and dimension zero (the vertices), and the complex generalizes this to higher dimensions. See also complex network, spectral graph theory, small-world network and the Watts-Strogatz model.
References
- Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press.
- Cayley, A. (1857). On the theory of the analytical forms called trees. Philosophical Magazine, series IV, 13(85), 172-176.
- Tutte, W. T. (2001). Graph Theory. Cambridge University Press, p. 30.
- West, D. B. (2001). Introduction to Graph Theory, 2nd ed. Prentice Hall, p. 20.
- Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G. (1994). Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications, 4, 235-282.
- Longabaugh, W. (2012). Combing the hairball with BioFabric. BMC Bioinformatics, 13, 275.
- Goodrich, M. T.; Tamassia, R. (2001). Estruturas de Dados e Algoritmos em Java, 2nd ed. Bookman, p. 502-503.
Source and licence
Translated and adapted from the article Teoria dos grafos on the Portuguese Wikipedia, checked against the revision of 6 October 2026, under the CC BY-SA 4.0 licence. I adapted the wording, corrected the history of the four colour problem and added the date of the proof. As a derivative work, this text is under the same licence.