The language of graphs

Graph theory is a branch of mathematics that studies systems by representing objects as vertices and relationships as edges. A graph is the mathematical structure

.

A vertex is a point in a graph representing an object or location. An edge connects two vertices and represents a relationship between them. Normally, neither the position of a vertex nor the shape or length of an edge on the page has any meaning unless the model explicitly assigns one. A transport diagram can therefore distort the geography while still preserving which stations are connected.

Two adjacent vertices are joined by an edge. Two adjacent edges share a common endpoint. The degree of a vertex counts the number of edge-ends incident with that vertex. We write it as

When loops are permitted, a loop contributes two to the degree because both ends meet the same vertex.

For any undirected graph,

Every edge contributes exactly two to the total degree, one at each end. It follows that the number of vertices with odd degree must be even.

Modelling real structures

When constructing a graph model, first choose what the vertices represent and what an edge means. Then decide whether the model needs direction or weights. In a water network, for instance, junctions could be vertices and pipes could be edges. A one-way valve requires a directed edge, while pipe length requires a weight.

An unweighted graph records only whether edges, and therefore connections, exist. In a weighted graph, each edge carries a numerical value for a quantity such as distance, journey time or cost. The units come from the context: distance might be measured in metres, time in seconds, and monetary cost in the relevant currency.

Abstraction deliberately leaves out some information. A circuit diagram preserves electrical connections rather than the physical positions of components. A transport map focuses on sequence and interchange instead of exact geography, while a structural formula shows how atoms are linked. A successful graph model retains the relationships needed to answer the question and ignores irrelevant detail.

Simple, complete and connected graphs

A simple graph is an undirected graph with no loops and no more than one edge between any pair of vertices. A complete graph is a simple graph in which every pair of distinct vertices is adjacent. We denote the complete graph on $n$ vertices by

It has $n(n-1)/2$ edges.

A connected graph is an undirected graph in which a route through edges exists between every pair of vertices. If not, the graph splits into connected components.

A subgraph is formed by selecting vertices and edges from another graph, with each selected edge keeping its original endpoints. It might represent one district of a network or just the part of a system needed for a particular calculation.

A tree is a connected simple graph with no cycles. Equivalently, a tree with $n$ vertices has $n-1$ edges, and exactly one path connects every pair of vertices. These viewpoints fit together: connectedness ensures that everything can be reached, while having no cycles means there is no redundant route.

Directed graphs

A directed graph, or digraph, has edges with orientations. A directed edge from vertex $u$ to vertex $v$ allows movement from $u$ to $v$, but it doesn’t automatically allow movement back. Here, $u$ and $v$ are endpoint vertices (unitless).

The in-degree of a vertex counts the directed edges entering it. It is written

The out-degree counts the directed edges leaving it. It is written

A directed loop contributes one to each.

A strongly connected graph is a directed graph in which every vertex can be reached from every other vertex by following the permitted directions. It isn’t enough for the graph to be connected only after the arrows are ignored.

Graphs link naturally to matrices. Once the vertices have been placed in a fixed order, rows and columns can store the edge information systematically. The next section develops this representation.

Representation, proof and knowledge

Symbolic maps are useful because they represent information selectively. Rather than reproducing physical appearance, they preserve connections and make complicated systems readable. Transit maps, chemical structures and electrical diagrams all use this same principle.

Graph theory also raises a deeper question about mathematical knowledge. The four-colour theorem states that no more than four colours are needed to colour any planar map so that regions sharing a boundary have different colours. Its proof depended on computer verification of many cases. This creates a genuine issue: must a person inspect every step directly for something to count as knowledge, or can confidence rely on a proved method, reliable software and independently checked computation? A correct output by itself isn’t a proof; the algorithm, assumptions and implementation all matter.

Adjacency matrices

An adjacency matrix is a square matrix showing which ordered pairs of vertices are connected. Choose a vertex order and state it first. For an unweighted graph, write

If rows represent starting vertices, then

In an undirected graph, $A$ is symmetric: an edge from $i$ to $j$ is also an edge from $j$ to $i$. Every diagonal entry of a simple graph is zero because loops are excluded. A directed graph, however, isn’t expected to give a symmetric matrix.

With this convention, row sums give out-degrees, while column sums give in-degrees. For an undirected graph, each row sum is simply the degree of the corresponding vertex. The matrix records the same relationships as the diagram in a form that can be used for calculations.

Undirected graph adjacency matrix in vertex order A, B, C, D, with symmetry and row sums matching degrees.

Walks and powers of the adjacency matrix

A walk is a sequence of vertices where each consecutive pair is joined by an appropriate edge. Vertices and edges may be repeated. Its length counts the number of edges traversed, not the number of vertices listed.

The main matrix result is that the $(i,j)$ entry of $A^k$ gives the number of walks of length $k$ from vertex $i$ to vertex $j$. Here, $A^k$ is the $k$th matrix power of $A$ (unitless), and $k$ is the required walk length, a non-negative integer (unitless). At each stage, matrix multiplication appends one permissible edge to a shorter walk.

To count walks with lengths from $1$ through $k$, take the corresponding entry of

For walks of length strictly less than $k$, use

Omit $I$ if the context excludes zero-length walks. Check the wording carefully: “less than $k$” and “at most $k$” ask for different things.

Weighted adjacency tables

A weighted adjacency table records the weight of the edge from vertex $i$ to vertex $j$ in its row-$i$, column-$j$ entry. Write it as

Show a missing direct edge with a dash or another clearly declared symbol rather than automatically using zero. Zero may be a legitimate weight; a blank indicates that the direct connection does not exist. The table is symmetric for an undirected weighted graph, but it need not be symmetric for a directed graph.

These tables support route calculations in road, airline and communication networks. They also make comparisons easier when numerical labels would clutter the graph diagram.

Transition matrices

A transition matrix is a square matrix whose entries show the probabilities of moving between vertices in one step. Keeping the row-as-source convention, define

Each row must sum to $1$.

For an unweighted directed graph where every outgoing edge is chosen with equal probability,

In an undirected graph, use the ordinary degree of the source vertex instead. If a graph is strongly connected, every vertex can eventually reach every other vertex; in particular, no vertex is trapped with no outgoing route.

If $\mathbf{p}_r$ is a row state vector, then

This connects transition matrices with Markov chains: the next state depends on the present probability distribution and the fixed transition rules.

Strongly connected digraph with row-stochastic transitions.

Page ranking as a graph model

In a page-ranking model, webpages are vertices and hyperlinks are directed edges. A basic transition matrix assumes that a user chooses equally among the links leaving the current page. Repeating the transitions shows which pages receive a larger long-run share of visits, providing one measure of importance. What matters is the structure of the links, not merely the number of pages.

Real web graphs can contain pages with no outgoing links or groups that trap movement, so practical ranking systems adjust the basic model. Even so, the simple graph version captures the central idea: convert a directed network into a transition matrix, then study it through repeated matrix multiplication.

The historical bridge-routing problem associated with Königsberg underwent a similar transformation. Geography was discarded, leaving only the land regions and bridge connections. This change of representation helped establish graph theory. The same lesson applies to airline networks and webpages: a suitable matrix can reveal patterns that are hard to spot in a picture alone.

Walks, trails, paths, circuits and cycles

These terms sound similar. To tell them apart, check what can repeat and whether the route is closed.

• A walk is a sequence of incident edges. Both vertices and edges may repeat.
• A trail is a walk with no repeated edges, though vertices may repeat.
• A path is a walk that does not repeat any vertex. As a result, no edge repeats either.
• A circuit is a closed trail: it begins and ends at the same vertex, with no edge repeated.
• A cycle is a closed path where only the initial and final vertex is repeated.

The tree and cycle algorithms in this topic use undirected graphs. Trees give connected networks with no redundant cycles; cycles give closed routes. Keep this distinction in mind when working through the algorithms.

Eulerian and Hamiltonian routes

An Eulerian trail uses every edge of a connected graph exactly once. An Eulerian circuit is an Eulerian trail that finishes at its starting vertex.

For a connected undirected graph, ignoring isolated vertices:

• an Eulerian circuit exists exactly when every vertex has even degree;
• an open Eulerian trail exists exactly when there are two odd-degree vertices, which must be its endpoints;
• neither exists if there are more than two odd-degree vertices.

The reason is local. Each time a route enters an intermediate vertex along one unused edge, it must leave along another. The incident edges therefore form pairs. Only the two endpoints of an open trail can have unpaired edges.

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once before returning to its starting vertex. Eulerian problems focus on every edge, whereas Hamiltonian problems focus on every vertex. No comparable degree test always determines whether a Hamiltonian path or cycle exists, so small cases are usually solved by systematic search or a specified algorithm.

Minimum spanning trees

A spanning tree is a subgraph of a connected graph that contains every vertex and is itself a tree. A minimum spanning tree, or MST, is the spanning tree with the smallest possible total edge weight. It connects every required location, has no cycle and contains one fewer edge than the number of vertices.

Kruskal’s algorithm

Kruskal’s algorithm builds a forest, considering edges across the whole graph from smallest weight to largest weight:

1. List or inspect all edges in increasing order of weight.
2. Add the next lightest edge unless doing so creates a cycle.
3. Continue until every vertex is connected and the chosen edges form a spanning tree.

When weights tie, the graph may have more than one MST. Either edge may be chosen as long as no cycle is created, but check the final total.

The method works because the cheapest edge joining two separate components can be added without losing the possibility of forming an MST. The cycle check matters. Simply choosing the lightest available edge each time can introduce redundancy.

Prim’s algorithm

Prim’s algorithm starts from one chosen vertex and grows a single connected tree:

1. Mark the starting vertex as included.
2. Choose the least-weight edge from an included vertex to a vertex not yet included.
3. Add the edge and the new vertex.
4. Repeat until all vertices have been included.

For the matrix method, use a weighted adjacency table. Cross out the row and column of each included vertex only in a way that still lets you inspect edges from the current tree to unvisited vertices. At each stage, choose the smallest eligible entry that crosses this boundary. Don’t select an edge between two vertices already in the tree, as this would create a cycle.

Both algorithms produce an MST, but they search differently. Kruskal considers edges throughout the graph, while Prim expands one connected component. They can model jobs such as installing cable or pipe with minimum total length. They don’t necessarily minimize the travel distance between every pair of vertices.

The Chinese postman problem

The Chinese postman problem asks for a closed walk of minimum total weight that traverses every edge of a connected weighted graph at least once. It models inspection, collection or delivery tasks in which every road segment must be covered.

Begin by finding the odd-degree vertices.

• If there are no odd vertices, the graph already has an Eulerian circuit. Use every edge once.
• If there are two odd vertices, find a shortest path between them and duplicate its edges. Both odd degrees then become even.
• If there are four odd vertices, list the three possible pairings. For each pairing, find and add the two relevant shortest-path weights. Duplicate the paths for the pairing with the smallest total added weight.

Once the edges have been duplicated, every vertex has even degree. The augmented connected graph therefore has an Eulerian circuit. Follow one such circuit, counting duplicated edges as separate traversals. The minimum route weight equals the total weight of all original edges plus the weight of the duplicated shortest paths.

The reasoning also shows why the algorithm works. Every vertex in a closed traversal needs even degree, so the odd vertices must be paired. A correction between two vertices must include a connecting route, and choosing a shortest route adds the least possible weight for that pairing. With four odd vertices, comparing every pairing gives the smallest valid correction.

The Chinese mathematician Kwan Mei-Ko formulated the problem in the twentieth century. Together with the earlier bridge-routing problem, it shows how local information about degree controls a global route.

The travelling salesman problem

The travelling salesman problem, or TSP, asks for a Hamiltonian cycle with the least total weight in a weighted complete graph. Each vertex is visited once before the route returns to its start.

A practical network may not be complete, since some pairs of locations have no direct connection. To convert it into the classical problem, construct a table of least distances. For every pair of required locations, enter the length of a shortest route through the original network. TSP algorithms can then be applied to the resulting complete weighted graph. An edge in this completed graph may stand for a multi-edge route in the original network.

Nearest neighbour upper bound

The nearest neighbour algorithm builds a feasible Hamiltonian cycle:

1. Choose a starting vertex.
2. Move to the nearest unvisited vertex.
3. Continue choosing the nearest unvisited vertex.
4. After every vertex has been visited, return to the starting vertex.

Since the result is a valid tour, its weight is an upper bound: a value known to be at least as large as the unknown optimum. Different starting vertices may give different tours. Repeating the algorithm from every possible start and keeping the lightest result will usually improve the bound, but it still doesn’t prove that the tour is optimal.

Deleted vertex lower bound

The deleted vertex algorithm gives a lower bound, which is a value known to be no greater than the optimum tour weight:

1. Delete one vertex and every edge incident with it.
2. Find an MST on the remaining vertices.
3. Add the weights of the two lightest edges connecting the deleted vertex to the remaining graph.

Every Hamiltonian cycle uses exactly two edges at the deleted vertex. Remove that vertex and its two incident tour edges, and the remaining structure still connects all other vertices. Its weight therefore cannot be less than the weight of their MST. So the MST weight plus the two lightest possible reconnection edges cannot exceed the optimal tour weight.

If requested, repeat the process using different deleted vertices. Every result is a valid lower bound, and the largest one is the strongest. When a feasible tour has the same weight as a valid lower bound, that tour must be optimal. No solution can fall below the lower bound, and none above the tour would improve it.

Least distances and TSP bounds for four vertices.

Applications and limitations

These algorithms are used in GPS routing, utility inspection and vehicle scheduling. Cycle models may also represent closed electrical loops, although graph structure alone cannot describe the physical meanings of current and voltage; additional circuit laws are needed.

Mathematics turns practical routing questions into precise optimization problems, but the model determines what “best” means. The shortest distance, least time, lowest cost and lowest emissions may lead to different routes. The TSP remains enduring because the number of possible tours increases extremely rapidly as more vertices are added. Informally, calling the general problem NP-hard means that no efficient exact algorithm is known for all cases, and that an efficient solution would resolve a much wider class of difficult computational problems. This makes heuristics and bounds valuable. They may not identify the optimum straight away, but they can give usable routes and indicate how far those routes could be from optimal.