Graph theory is the mathematics of relationships. It represents entities as vertices and connections as edges, turning networks into objects that can be measured, searched, optimised and proved.
Road systems, airline routes, friendship networks, electrical grids, internet links, dependency maps and molecular structures can all be modelled as graphs. The physical meanings differ, but questions about connection, reachability, bottlenecks, shortest routes and resilience often share the same mathematical structure.
Series route: Mathematics Learning Hub → How Mathematics Works → Graph Theory.
1. What a graph is
A graph consists of a set of vertices and a set of edges connecting selected pairs of vertices. The graph may be directed or undirected, weighted or unweighted, simple or allow multiple edges depending on the model.
2. Modelling comes before calculation
The first graph-theory decision is what a vertex and edge mean. A city network can use stations as vertices and tracks as edges; a timetable conflict graph can use exams as vertices and student overlap as edges.
A wrong graph definition produces a mathematically correct answer to the wrong system.
3. Degree measures local connection
The degree of a vertex counts incident edges. In directed graphs, indegree and outdegree distinguish incoming from outgoing connections.
Degree is local. A highly connected vertex may be important, but network importance can also depend on position rather than raw connection count.
4. Paths describe reachability
A path is a sequence of adjacent vertices. If a path exists between two vertices, one is reachable from the other under the graph’s direction rules.
Reachability is a foundational network question because many other problems begin by asking whether connection exists at all.
5. Connectivity measures whether the network stays in one piece
An undirected graph is connected when every pair of vertices can be joined by a path. Directed graphs use stronger notions such as strong connectivity.
Connectivity turns a visual network into a precise structural property.
6. Components are isolated sub-networks
A disconnected graph splits into connected components. Each component is internally reachable but isolated from the others.
Finding components can reveal fragmented social groups, disconnected infrastructure or separate clusters in data.
7. Cycles represent return paths
A cycle is a closed route that returns to its starting point under the graph’s rules. Cycles can represent redundancy, feedback or loop structure.
Whether cycles are desirable depends on context. They add route redundancy in transport but can create dependency loops in software.
8. Trees are connected graphs without cycles
A tree connects all its vertices without loops. For n vertices, a finite tree has n−1 edges.
Trees model hierarchies, search structures and minimal connection systems.
9. Spanning trees remove redundancy while preserving connection
A spanning tree of a connected graph includes every vertex with just enough edges to remain connected.
A minimum spanning tree chooses the lowest-cost such structure when edges carry weights.
10. Shortest paths optimise travel through weighted networks
Shortest-path problems ask for a path minimising total edge cost. The cost may represent distance, time, money, risk or another quantity.
Algorithms such as Dijkstra’s method exploit local optimality conditions when edge weights satisfy the required assumptions.
11. Negative weights change the algorithm
Algorithms are tied to assumptions. Dijkstra’s algorithm does not generally support negative edge weights. Bellman–Ford-type methods can handle them and detect negative cycles.
Graph theory teaches an important algorithmic lesson: the right method depends on the structural properties of the graph.
12. Euler trails use every edge
An Euler trail traverses every edge exactly once. Euler’s analysis of the Königsberg bridges helped launch graph theory by showing that such route questions depend on vertex degrees, not geometric distances.
13. Hamiltonian paths use every vertex
A Hamiltonian path visits every vertex exactly once. This looks similar to an Euler problem but is structurally different.
The travelling-salesperson problem is closely related and illustrates how simple graph questions can become computationally difficult.
14. Graph colouring allocates incompatible resources
A proper vertex colouring assigns colours so adjacent vertices differ. Colours can represent time slots, radio frequencies or other mutually exclusive resources.
The chromatic number is the smallest number of colours needed.
15. Matchings create compatible pairings
A matching is a collection of edges that share no vertices. Bipartite matching models assignments between two classes, such as workers and jobs.
Maximum matching finds the largest feasible set of nonconflicting pairings.
16. Network flows move capacity through graphs
Flow networks assign capacities to directed edges. The maximum-flow problem asks how much can be transported from a source to a sink without violating capacities.
The max-flow min-cut theorem links optimal throughput to the smallest separating bottleneck.
17. Cuts reveal vulnerability
A cut separates a graph into parts. Small cuts reveal structural bottlenecks where failure of a few edges or vertices can fragment the network.
This matters in transport, communications, power networks and resilience planning.
18. Centrality measures different kinds of importance
Degree centrality measures local connection. Betweenness centrality measures how often a vertex lies on shortest routes. Closeness and eigenvector-type centralities capture other structural roles.
There is no universal “most important node.” Importance depends on the question.
19. Adjacency matrices translate graphs into linear algebra
An adjacency matrix records which vertices are connected. Matrix powers can count walks, while eigenvalues reveal global structural properties.
Spectral graph theory uses this bridge to study networks algebraically.
20. Random graphs model network formation
Random graph models assign probability to edges or structures. They help study threshold effects such as when a large connected component suddenly emerges.
This creates a bridge to probability and statistical network science.
21. Planar graphs respect embedding constraints
A planar graph can be drawn in the plane without crossing edges. Euler-type formulas relate vertices, edges and faces in connected planar graphs.
Planarity connects graph theory with topology and geometry.
22. A worked mechanism: timetable conflicts
Suppose exams are vertices and an edge connects two exams sharing at least one student.
- Build the conflict graph.
- Assign each time slot a colour.
- Adjacent exams must have different colours.
- The smallest feasible colouring minimises the number of slots in the simplified model.
23. Common failure modes
- Model mismatch: vertices or edges do not encode the real constraint.
- Directed/undirected confusion: treating asymmetric relations as symmetric.
- Weight blindness: counting edges when cost depends on weights.
- Path/trail confusion: mixing vertex and edge restrictions.
- Algorithm-assumption failure: using a method outside the graph class it supports.
- Centrality overclaim: treating one score as universal importance.
24. Graph theory and combinatorics
Graphs are combinatorial objects. Colourings, matchings and subgraphs are counting problems under structural constraints.
25. Graph theory and linear algebra
Adjacency and Laplacian matrices translate networks into matrix structure. Eigenvalues help study connectivity, diffusion and clustering.
26. Graph theory in civilisation
Transport, logistics, communications, supply chains and institutions are relational systems. Graph theory gives civilisation a mathematical language for connection, redundancy, bottlenecks and routing.
27. Graph theory as a machine
Entities → Edges/Weights → Paths/Components → Algorithm or Invariant → Bottleneck/Optimal Structure → Interpretation.
28. What mastery looks like
- choose vertices and edges that match the real system;
- distinguish connectivity, reachability and path constraints;
- work with trees, cycles, matchings and colourings;
- apply shortest-path, spanning-tree and flow ideas with correct assumptions;
- read cuts as resilience information;
- use matrix representations when helpful;
- recognise that network importance is context-dependent;
- return graph answers to the physical or institutional system.
29. Conclusion
Graph theory works by turning relationships into mathematical structure. Vertices represent entities, edges represent connections, paths represent reachability, cuts expose bottlenecks, flows measure capacity, colourings allocate incompatible resources and matchings coordinate assignments.
Combinatorics counts possibilities. Graph theory gives those possibilities a network.
How Mathematics Works | Batch 05
- How Mathematics Works | Combinatorics
- Graph Theory — this article
- How Mathematics Works | Measure Theory
- How Mathematics Works | Differential Geometry
Return to the Mathematics Learning Hub or the How Mathematics Works root.