Graph Theory Fundamentals

Graph theory is a branch of mathematics that studies structures called graphs, which model pairwise relationships between objects. Unlike the coordinate graphs you may have used to plot functions, a graph in this sense is an abstract network of points connected by lines. Graph theory underpins technologies you use every day: GPS navigation finds the shortest path through a road network, social media platforms analyse friend connections, and computer networks route data packets — all using graph-theoretic ideas. Formally, a graph G is defined as an ordered pair G = (V, E), where V is a non-empty set of vertices (also called nodes) and E is a set of edges, each edge being an unordered pair {u, v} of distinct vertices. The vertices represent objects, and the edges represent relationships or connections between them. For example, if V = {A, B, C, D} and E = {{A,B}, {B,C}, {C,D}, {A,D}}, we have a cycle of four vertices. This simple framework is powerful enough to model road maps, family trees, molecular structures, and scheduling problems. Within optimisation and mathematical modelling, graph theory provides tools to answer questions such as: What is the minimum cost to connect all cities in a network? Can a delivery driver visit every location exactly once and return home? Is it possible to colour a map so no two neighbouring regions share the same colour? These questions translate into precise graph-theoretic problems with elegant mathematical solutions, many of which have profound real-world impact.

Key takeaways
  • Vertices, Edges, and Adjacency
  • Degree of a Vertex
  • Simple, Complete, and Weighted Graphs
  • Directed Graphs (Digraphs)
  • Subgraphs and Trees

Vertices, Edges, and Adjacency

A vertex u and a vertex v are said to be adjacent if there exists an edge {u, v} connecting them. The edge {u, v} is then said to be incident to both u and v. Two edges that share a common vertex are called incident edges. The neighbourhood N(v) of a vertex v is the set of all vertices adjacent to v. For example, in the graph where V = {1, 2, 3, 4} and E = {{1,2},{1,3},{2,4}}, vertex 1 is adjacent to vertices 2 and 3, so N(1) = {2, 3}.

Degree of a Vertex

The degree of a vertex v, written deg(v) or d(v), is the number of edges incident to it — equivalently, the number of neighbours it has. In the example above, deg(1) = 2, deg(2) = 2, deg(3) = 1, deg(4) = 1. The Handshaking Lemma states that the sum of all vertex degrees equals twice the number of edges: \sum_{v \in V} \deg(v) = 2|E|. This follows because every edge contributes exactly 1 to each of its two endpoints' degrees. A direct corollary is that every graph has an even number of odd-degree vertices.

Simple, Complete, and Weighted Graphs

A simple graph has no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices. A complete graph K_n has n vertices and every possible edge between distinct vertices, giving |E| = n(n-1)/2 edges. For instance, K_4 has 4 vertices and 6 edges. A weighted graph assigns a numerical weight w(e) to each edge e — this weight might represent distance, cost, or travel time. Weighted graphs are essential in shortest-path algorithms such as Dijkstra's algorithm, where the goal is to minimise the total weight of a path from a source to a destination.

Directed Graphs (Digraphs)

In a directed graph (digraph), each edge is an ordered pair (u, v), called an arc, indicating a one-way connection from u to v. The in-degree of a vertex is the number of arcs pointing into it; the out-degree is the number pointing out. Digraphs model asymmetric relationships: one-way streets, web page hyperlinks, or prerequisite chains between courses. The Handshaking Lemma for digraphs states that the sum of all in-degrees equals the sum of all out-degrees, both equalling the total number of arcs |E|.

Subgraphs and Trees

A subgraph H of G is a graph whose vertex set V(H) ⊆ V(G) and edge set E(H) ⊆ E(G). A spanning subgraph includes all vertices of G. A graph is connected if there is a path between every pair of vertices. A tree is a connected graph with no cycles; it satisfies |E| = |V| − 1. Trees are the 'leanest' connected graphs — removing any edge disconnects them, and adding any edge creates a cycle. A spanning tree of a connected graph G is a subgraph that is a tree and includes all vertices. Finding a minimum spanning tree (one minimising total edge weight) is a classic optimisation problem solved by Kruskal's or Prim's algorithm.

The Key Equation

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|
  • V — Vertex set (dimensionless): The set of all vertices (nodes) in the graph G.
  • \deg(v) — Degree of vertex v (dimensionless): The number of edges incident to vertex v; equivalently, the size of its neighbourhood |N(v)|.
  • |E| — Number of edges (dimensionless): The total count of edges (connections) in the graph G.

Worked Example

Problem. Consider the complete graph K_5. (a) How many edges does K_5 have? (b) What is the degree of each vertex? (c) Verify the Handshaking Lemma for K_5.

∣E∣=5×42=10,deg⁡(v)=4 for all v,∑vdeg⁡(v)=20=2∣E∣|E| = \frac{5 \times 4}{2} = 10, \quad \deg(v) = 4 \text{ for all } v, \quad \sum_{v} \deg(v) = 20 = 2|E|

Answer. K_5 has 10 edges; every vertex has degree 4; the sum of degrees is 20 = 2 × 10, confirming the Handshaking Lemma.

Figure
Diagram
Graph Theory: Simple Graph, K₄, and a TreeSimple Graph GABCDdeg(A)=2, deg(B)=2deg(C)=2, deg(D)=2Σdeg=8=2×4 ✓Complete Graph K₄12346 edges, each deg=3Σdeg=12=2×6 ✓Tree (5 vertices)RSTUW4 edges = |V|−1Connected, no cyclesLeft: simple graph | Centre: complete graph K₄ | Right: spanning tree
Origins · 1 minLeonhard Euler and how this was discovered
LE
Leonhard Euler
1707–1783 · Swiss

Euler founded graph theory in 1736 by solving the famous Königsberg Bridge Problem. The city of Königsberg (now Kaliningrad) had seven bridges connecting two islands and two riverbanks. Euler asked: can one walk through the city crossing each bridge exactly once? He represented the landmasses as vertices and bridges as edges, proving such a walk (now called an Eulerian path) is possible if and only if the graph has exactly 0 or 2 vertices of odd degree. Since Königsberg's graph had four odd-degree vertices, no such walk existed. This work, published in his paper 'Solutio problematis ad geometriam situs pertinentis,' introduced the very concept of a graph. Euler lost sight in his right eye at age 31 and became almost totally blind by age 59, yet he produced roughly half of his total mathematical output after losing his sight — dictating solutions to scribes. He is considered the most prolific mathematician in history.

  • Shortest Path Algorithms — Dijkstra's and Bellman–Ford algorithms operate directly on weighted graphs to find minimum-weight paths between vertices, applying the edge and vertex framework introduced here.
  • Minimum Spanning Trees — Kruskal's and Prim's algorithms find the spanning tree of minimum total edge weight, building directly on the definitions of trees, subgraphs, and edge weights covered in this article.
  • Combinatorics and Counting Principles — The formula for edges in K_n uses combinations C(n,2), and many graph problems — such as counting paths or colourings — rely on combinatorial reasoning.
  • Matrices and Linear Algebra — An adjacency matrix encodes a graph's structure numerically: entry A_{ij} = 1 if edge {i,j} exists. Matrix multiplication then reveals the number of paths of given lengths, linking graph theory to linear algebra.