You have already seen a graph today. The web of links between Wikipedia pages. Your social feed where some people follow you and you do not follow back. The map app that found you a shorter route to work. All of them share a single underlying abstraction: a collection of things with connections between them. Mathematicians formalised this idea 300 years ago when Leonhard Euler asked whether you could cross every bridge in Königsberg exactly once and return to where you started. That puzzle gave us graph theory.
What Is a Graph?
A graph is a pair of sets: G = (V, E). V is the set of vertices (also called nodes). E is the set of edges (the connections between vertices). An edge is an unordered pair of vertices: if you have vertices called Alice and Bob, the edge means they are connected.
That is the whole definition. Everything else in graph theory is about asking interesting questions of this simple structure.
Vertices vs Nodes
The terms are interchangeable. Computer scientists tend to say "nodes". Mathematicians and physicists tend to say "vertices". You will see both in the wild. This article uses them interchangeably.
The Size of a Graph
Quantity
Notation
Meaning
Number of vertices
|V| or n
The order of the graph
Number of edges
|E| or m
The size of the graph
A graph with n vertices could have anywhere from zero edges to roughly n squared edges, depending on what kind of graph it is.
Directed vs Undirected Graphs
This is the first big fork in the road.
Undirected graphs have edges with no direction. An edge is a two-way street. If Alice and Bob are connected, either can reach the other. Think of Facebook friendships: if you are friends with someone, they are friends with you.
Directed graphs (digraphs) have edges with an arrow. Each edge goes from one vertex to another. You can have an edge from Alice to Bob without Bob having one back to Alice. Think of Twitter follows: you can follow someone who does not follow you.
Property
Undirected
Directed
Edge notation
(u, v)
Symmetry
Always symmetric
May be asymmetric
Real example
Facebook friends
Twitter follows
Common use case
Road networks (two-way streets)
Web page links, payment flows
Some graphs are neither fully directed nor fully undirected. A mixed graph has both types of edges, though they are less common in practice.
Weighted vs Unweighted Graphs
An edge can carry extra information called a weight. In a road network, the vertices are intersections and the edge weights are distances. Your satnav finds the path with the smallest total weight.
Unweighted graphs treat every edge as having equal cost. When you use BFS to find the shortest number of hops between two people in a social network, you are working with an unweighted graph.
Signed Graphs
Occasionally you see graphs with positive and negative edge weights. These model friendly and hostile relationships, or trust and distrust in a recommendation system.
Loops and Multigraphs
A loop is an edge that connects a vertex to itself. A simple graph bans loops.
A multigraph allows multiple edges between the same two vertices. Why would you need this? Consider a map of airline routes between cities. If two airlines fly the same route, that might be represented as two parallel edges. Or consider a collaboration network where two researchers co-author multiple papers.
A simple graph bans both loops and multiple edges. Most of graph theory starts with simple graphs and adds complexity from there.
Degree, In-Degree, Out-Degree
The degree of a vertex is the number of edges incident to it. In a directed graph, you split this into in-degree (edges coming in) and out-degree (edges going out). A Twitter user followed by 500 people and following 200 has in-degree 500 and out-degree 200.
The Handshake Lemma
This is the first theorem worth remembering. The sum of the degrees of all vertices in an undirected graph equals twice the number of edges.
sum of degrees = 2 * |E|
Why? Every edge contributes to the degree of two vertices. Count carefully and you get a factor of two. This lemma appears everywhere. It tells you immediately that the number of vertices with odd degree must be even.
In a directed graph, the sum of in-degrees equals the sum of out-degrees, and both equal |E|.
Walks, Trails, Paths, Cycles
The terminology here is precise. Each term adds a stricter constraint.
A walk is any sequence of vertices where each consecutive pair is connected by an edge. You can revisit vertices and reuse edges as much as you like.
A trail is a walk that does not reuse any edge. You can revisit vertices but not edges.
A path is a trail that does not revisit any vertex. This is what most people mean when they say "find a path from A to B." It is a simple, non-repeating route.
A cycle is a path that starts and ends at the same vertex, with at least one edge. Think of a loop you can walk around and return to where you began.
Term
Reuse vertices?
Reuse edges?
Start = End?
Walk
Yes
Yes
Optional
Trail
Yes
No
Optional
Path
No
No
No
Cycle
Only the start/end
No
Yes
Connectivity
A graph is connected if there is a path between every pair of vertices. You can get from any vertex to any other vertex.
A disconnected graph falls apart into pieces. Each piece is a connected component. A graph with three islands has three connected components.
For directed graphs, connectivity is more subtle. A digraph is strongly connected if there is a directed path from any vertex to any other vertex in both directions. It is weakly connected if ignoring direction makes the underlying undirected graph connected.
Connected Components in Practice
When a deployment tool analyses a microservice architecture, it might find one giant connected component of services that talk to each other, plus a few isolated services. Each isolated group is its own connected component.
Special Graph Families
Some graphs appear so often that they have their own names.
Complete Graphs Kₙ
Every vertex is connected to every other vertex. K₅ has five vertices, each joined to the other four. The number of edges in Kₙ is n(n-1)/2. Complete graphs are the densest possible simple graphs.
Bipartite Graphs
You can split the vertices into two groups such that every edge crosses from one group to the other. No edge connects two vertices inside the same group. Many real problems are bipartite: users and the movies they rate, job applicants and positions, patients and symptoms.
Trees
A tree is a connected graph with no cycles. It is the minimal way to connect all vertices. Trees show up everywhere: file systems, organisational hierarchies, parse trees in compilers, spanning trees in network routing.
A forest is a disjoint union of trees (a disconnected acyclic graph).
Property
Tree
Forest
Connected?
Yes
No
Has cycles?
No
No
Edges relative to vertices
|E| = |V| - 1
|E| = |V| - (number of trees)
Spanning Trees
A spanning tree of a connected graph includes all its vertices but only enough edges to stay connected and acyclic. A minimum spanning tree (MST) is the spanning tree with the smallest total edge weight — the cheapest way to connect everything.
MST algorithms are workhorses of network design. Kruskal's algorithm sorts edges by weight and adds them one by one, skipping any that would create a cycle. Prim's algorithm grows a tree from a starting vertex, always adding the cheapest edge that connects a new vertex. Both run in O(m log n) time on practical graphs, used daily in fibre-optic trenching, circuit layout, and single-linkage clustering.
Cycle Graphs Cₙ
A cycle graph is a single loop of n vertices, each connected to exactly two neighbours. C₃ is a triangle, C₄ is a square, C₅ is a pentagon.
Graph Colouring
A graph colouring assigns colours to vertices so that no two adjacent vertices share the same colour. The minimum number of colours required is the graph's chromatic number.
The four colour theorem — that every planar map can be coloured with at most four colours — took 124 years to prove and was the first major theorem proven with computer assistance. In practice, graph colouring solves scheduling problems: exam timetables where no student has two exams simultaneously, register allocation in compilers, and frequency assignment in cellular networks where nearby towers must use different channels.
Graph Isomorphism
Two graphs are isomorphic if they are the same graph drawn differently. The vertex labels do not matter. What matters is the pattern of connections.
Take a triangle graph. Whether you draw it as an equilateral triangle, a squashed triangle, or three points connected by curved lines, the underlying graph is the same: each vertex connects to the other two.
Determining whether two arbitrary graphs are isomorphic is a famously difficult problem. No one knows whether it can be solved in polynomial time in general, though it is almost certainly not NP-complete. For small graphs you can often tell by comparing degree sequences, but for large graphs the problem remains tantalisingly open.
Adjacency Matrix vs Adjacency List
When you need to store a graph in a computer, you have two main choices.
An adjacency matrix is a |V| by |V| grid where cell [i][j] is 1 if there is an edge from vertex i to vertex j. Lookups are instant. But the matrix takes O(|V|²) space regardless of how many edges you actually have. For a sparse graph with millions of vertices and only a few edges each, that is wasteful.
An adjacency list stores for each vertex a list of its neighbours. Space scales with |V| + |E|. Iterating over a vertex's neighbours is fast. Checking whether a specific edge exists is slower, but that is rarely the bottleneck.
Consideration
Adjacency Matrix
Adjacency List
Space
O(V²)
O(V + E)
Edge lookup
O(1)
O(degree(v))
Iterate neighbours
O(V)
O(degree(v))
Best for
Dense graphs, quick edge checks
Sparse graphs, traversals
For almost all real-world graphs, the adjacency list wins because real graphs are sparse. The Twitter follow graph has hundreds of millions of vertices, but each user follows only a tiny fraction of everyone else.
Graphs in Code
Both representations are straightforward to implement. An adjacency list in Python uses a dictionary mapping vertices to neighbour lists:
A depth-first search traverses this structure to reveal connectivity:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbour in graph[start]:
if neighbour not in visited:
dfs(graph, neighbour, visited)
return visited
For weighted graphs, store (neighbour, weight) tuples. This pattern powers graph databases: Neo4j and Amazon Neptune store variants of adjacency lists optimised for disk and parallel traversal.
Subgraphs and Graph Minors
A subgraph is a graph formed by taking a subset of vertices and a subset of edges that only use those vertices. If you delete some vertices (and the edges attached to them), you get an induced subgraph.
A graph minor is what you get when you contract edges (merge two vertices into one) or delete vertices and edges. Minors matter in deep structural graph theory. The famous Robertson-Seymour theorem says that every family of graphs closed under taking minors can be characterised by a finite set of forbidden minors. It took twenty papers and 500 pages to prove.
Why This Matters
Everything else in graph theory and graph algorithms builds on these foundations. If you are working with graphs in production, every concept in this article maps directly to practice:
Knowledge graphs use nodes and edges to model entities and their relationships — the same V and E from section one. The Ontology in Graph Databases article shows how this plays out in production.
Graph databases like Neo4j are optimised adjacency lists, storing neighbour pointers directly on disk so traversals never pay for full-table scans.
GraphRAG retrieves information by traversing entity relationships rather than relying on vector similarity alone. The Introduction to GraphRAG article explains the architecture.
Path-finding algorithms — Dijkstra, A*, BFS — all operate on the same walk, path, and cycle definitions covered here.
In the companion article, Graph Theory for Software Engineers, you will see how BFS and DFS traverse these structures, how shortest-path algorithms find routes through weighted graphs, and how centrality metrics identify important nodes.
Graph theory starts with a deceptively simple idea: things and their connections. From that seed grows an entire field that models the internet, the brain, social networks, logistics, protein interactions, and the structure of knowledge itself.