Loading learning content...
In the previous page, we developed intuition for vertices and edges as the building blocks of graphs. Now, we elevate that understanding to the level of mathematical precision. Why does this matter? Because precise definitions enable:
The notation G = (V, E) is the universal language of graph theory. Mastering it allows you to read academic papers, understand algorithm specifications, and communicate with precision about any graph-related concept.
By the end of this page, you will understand the formal mathematical definition of a graph, interpret set notation for vertices and edges, distinguish between different graph formalizations, and feel confident reading graph definitions in academic or technical literature.
A graph is formally defined as an ordered pair:
$$G = (V, E)$$
where:
This deceptively simple definition encapsulates everything about a graph's structure. Let's unpack each component carefully.
We write G = (V, E) as an ordered pair because V and E play fundamentally different roles. V defines the universe of entities; E defines relationships between them. The order matters conceptually: edges reference vertices, not the reverse.
The Vertex Set V:
V is a set, meaning:
The elements of V can be anything—integers, strings, objects—as long as they are distinguishable. In formal mathematics, we often use:
The Edge Set E:
E is also a set, but its elements are pairs of vertices. The exact nature of these pairs depends on whether the graph is directed or undirected (we'll formalize this shortly).
12345678910111213141516
Example Graph G = (V, E) Vertex set: V = {1, 2, 3, 4, 5} |V| = 5 (cardinality: number of vertices) Edge set (undirected): E = {{1,2}, {1,3}, {2,3}, {3,4}, {4,5}} |E| = 5 (cardinality: number of edges) Interpretation: - There are 5 vertices labeled 1 through 5 - There are 5 undirected edges connecting pairs of vertices - Vertex 1 is connected to vertices 2 and 3 - Vertex 3 is connected to vertices 1, 2, and 4 - Vertex 5 is only connected to vertex 4In an undirected graph, edges have no direction—the relationship is symmetric. If there's an edge between A and B, you can traverse it from A to B or from B to A.
Formal Definition:
An undirected graph G = (V, E) is defined where:
Each edge e ∈ E is an unordered pair of distinct vertices, written as {u, v} or simply (u, v) when context is clear.
Key Property: For an undirected edge {u, v}, we have {u, v} = {v, u}. The edge "from u to v" is identical to the edge "from v to u".
Set notation explanation:
| Property | Description | Example |
|---|---|---|
| Symmetry | {u, v} = {v, u} | {A, B} and {B, A} are the same edge |
| Unordered | No 'from' or 'to' endpoint | Just 'connected' |
| Maximum edges | n(n-1)/2 for n vertices | 5 vertices → max 10 edges |
| Self-loops | Excluded in simple graphs | {A, A} not allowed |
Facebook friendships are undirected: if Alice is friends with Bob, Bob is friends with Alice. Road segments in a city (ignoring one-way streets) are undirected: you can drive either direction. Physical cables connecting computers are undirected: data flows both ways.
In a directed graph (also called a digraph), edges have direction—they point from one vertex to another. The relationship is not necessarily symmetric.
Formal Definition:
A directed graph G = (V, E) is defined where:
Each edge e ∈ E is an ordered pair (u, v), meaning there is a directed edge from u to v.
Key Property: For a directed edge (u, v), we have (u, v) ≠ (v, u) in general. The edge from u to v is distinct from the edge from v to u.
Terminology:
1234567891011121314151617181920
Directed Graph G = (V, E) Vertex set: V = {A, B, C, D} Edge set (directed, ordered pairs): E = {(A, B), (A, C), (B, C), (C, D), (D, B)} Interpretation: - Edge (A, B): A → B (can go from A to B, not B to A via this edge) - Edge (B, C): B → C - Edge (D, B): D → B (creates a cycle: B → C → D → B) Note: There is no edge (B, A), so you cannot go directly from B to A. Visual representation: A → B ↓ ↑↖ C → D (D points back to B, C points to D)When analyzing graphs, we frequently need to refer to the number of vertices and edges. Standard notation provides convenient shorthand:
Cardinality Notation:
Both n and m are commonly used in algorithm complexity analysis. You'll see expressions like:
Bounds on Edge Count:
For a simple undirected graph (no self-loops, no duplicate edges): $$0 \leq |E| \leq \binom{n}{2} = \frac{n(n-1)}{2}$$
For a simple directed graph (no self-loops, at most one edge per direction): $$0 \leq |E| \leq n(n-1)$$
For a directed graph with self-loops: $$0 \leq |E| \leq n^2$$
| Graph Type | Maximum |E| | Formula | For n=10 |
|---|---|---|---|
| Simple undirected | n(n-1)/2 | C(n,2) | 45 |
| Simple directed | n(n-1) | All ordered pairs, no self-loops | 90 |
| Directed with self-loops | n² | Full Cartesian product | 100 |
| Undirected with self-loops | n(n-1)/2 + n | Pairs + self-loops | 55 |
In complexity analysis, you'll often see both O(V + E) and O(n + m) used interchangeably. The letter convention (n, m) is common in theoretical computer science, while (V, E) is common in textbooks and practical algorithm descriptions. Both mean the same thing.
Graph theory uses specific terminology to describe graph dimensions:
Order of a Graph:
The order of a graph G is the number of vertices: $$\text{order}(G) = |V|$$
A graph with n vertices is called a graph of order n.
Size of a Graph:
The size of a graph G is the number of edges: $$\text{size}(G) = |E|$$
A graph with m edges is called a graph of size m.
Examples:
123456789101112131415161718192021222324252627282930
Complete Graph Kₙ: - Every vertex connected to every other vertex - Order: n - Size: n(n-1)/2 K₃ (Triangle): Order = 3, Size = 3 K₄: Order = 4, Size = 6 K₅: Order = 5, Size = 10 K₁₀₀: Order = 100, Size = 4,950 Path Graph Pₙ: - n vertices in a line, no cycles - Order: n - Size: n-1 P₃: 1 — 2 — 3 Order = 3, Size = 2 P₅: 1 — 2 — 3 — 4 — 5 Order = 5, Size = 4 Cycle Graph Cₙ: - n vertices in a cycle - Order: n - Size: n C₃ (Triangle): Order = 3, Size = 3 C₆: Order = 6, Size = 6 Null/Empty Graph Nₙ: - n isolated vertices, no edges - Order: n - Size: 0When someone says 'a graph of order 6 and size 8,' they mean 6 vertices and 8 edges. This terminology is common in mathematical graph theory literature.
Because graphs are defined using sets, we can apply set operations to combine or compare graphs. This is particularly useful in graph algorithms and theoretical analysis.
Subgraph:
A graph H = (V', E') is a subgraph of G = (V, E) if:
Induced Subgraph:
Given a vertex subset S ⊆ V, the induced subgraph G[S] is:
This is the subgraph you get by selecting vertices and keeping all edges between them.
Edge-Induced Subgraph:
Given an edge subset F ⊆ E, the edge-induced subgraph includes:
12345678910111213141516171819
Original Graph G: V = {A, B, C, D, E} E = {(A,B), (A,C), (B,C), (B,D), (C,D), (D,E)} Subgraph H (selecting vertices {A, B, C}): V' = {A, B, C} E' = {(A,B), (A,C), (B,C)} ← All edges within {A,B,C} This is the induced subgraph G[{A,B,C}] Subgraph H₂ (arbitrary, not induced): V' = {A, B, C} E' = {(A,B), (B,C)} ← Missing (A,C) This is a valid subgraph but NOT induced (we dropped edge (A,C)) Edge-Induced Subgraph on {(B,D), (D,E)}: V' = {B, D, E} ← Only vertices appearing in the selected edges E' = {(B,D), (D,E)}Subgraph operations are fundamental to many algorithms. Finding connected components, detecting cliques, and graph partitioning all involve reasoning about subgraphs. The induced subgraph concept is especially important in NP-hard problems like finding the largest clique.
When are two graphs "the same"? This question has two distinct answers depending on what we mean:
Graph Equality:
Two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are equal if and only if:
This is the strictest form of sameness—the graphs are literally identical.
Graph Isomorphism:
Two graphs G₁ and G₂ are isomorphic (written G₁ ≅ G₂) if there exists a bijection (one-to-one mapping) f: V₁ → V₂ such that:
In plain language: we can relabel the vertices of G₁ to get G₂. The graphs have the same "shape" even if the labels differ.
12345678910
Graph G₁: V₁ = {1, 2, 3} E₁ = {(1,2), (2,3)} Graph G₂: V₂ = {1, 2, 3} E₂ = {(1,2), (2,3)} G₁ = G₂? YESSame vertices, same edges.1234567891011
Graph G₁: V₁ = {1, 2, 3} E₁ = {(1,2), (2,3)} Graph G₂: V₂ = {A, B, C} E₂ = {(A,B), (B,C)} G₁ ≅ G₂? YESMapping: 1→A, 2→B, 3→CSame structure, different labels.Determining whether two graphs are isomorphic (the Graph Isomorphism problem) is computationally challenging. It's not known to be solvable in polynomial time for general graphs, though efficient algorithms exist for special cases. This is one of the few natural problems not known to be in P or NP-complete.
The formal definition G = (V, E) directly informs how we implement graphs in code. Each representation choice reflects decisions about how to store V and E:
Storing the Vertex Set V:
Storing the Edge Set E:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
from typing import Set, Tuple, List, Dict # Mathematical definition: G = (V, E)# Example: V = {0, 1, 2, 3}, E = {(0,1), (0,2), (1,2), (2,3)} # Representation 1: Edge List (direct translation of E)class GraphEdgeList: """G = (V, E) where we store E explicitly as a list.""" def __init__(self, num_vertices: int, edges: List[Tuple[int, int]]): self.n = num_vertices # |V| = n, V = {0, 1, ..., n-1} self.edges = edges # E stored as list of tuples def has_edge(self, u: int, v: int) -> bool: return (u, v) in self.edges or (v, u) in self.edges # O(|E|) # Representation 2: Adjacency List (efficient neighbor lookup)class GraphAdjList: """G = (V, E) stored as vertex → neighbors mapping.""" def __init__(self, num_vertices: int): self.n = num_vertices self.adj: Dict[int, Set[int]] = {v: set() for v in range(num_vertices)} def add_edge(self, u: int, v: int): self.adj[u].add(v) self.adj[v].add(u) # Undirected: add both directions def has_edge(self, u: int, v: int) -> bool: return v in self.adj[u] # O(1) average with set # Representation 3: Adjacency Matrixclass GraphAdjMatrix: """G = (V, E) stored as n×n boolean matrix.""" def __init__(self, num_vertices: int): self.n = num_vertices self.matrix = [[False] * num_vertices for _ in range(num_vertices)] def add_edge(self, u: int, v: int): self.matrix[u][v] = True self.matrix[v][u] = True # Undirected def has_edge(self, u: int, v: int) -> bool: return self.matrix[u][v] # O(1) # Example usage with G = (V, E)# V = {0, 1, 2, 3}, E = {(0,1), (0,2), (1,2), (2,3)}edges = [(0, 1), (0, 2), (1, 2), (2, 3)] # Create all three representationsg1 = GraphEdgeList(4, edges)g2 = GraphAdjList(4)g3 = GraphAdjMatrix(4) for u, v in edges: g2.add_edge(u, v) g3.add_edge(u, v) # All three represent the same graph G = (V, E)print(g1.has_edge(0, 1)) # Trueprint(g2.has_edge(0, 1)) # Trueprint(g3.has_edge(0, 1)) # TrueWe've established the rigorous mathematical foundation for graphs. Let's consolidate the key concepts:
What's Next:
Now that we have the formal framework, we'll explore the relationships between vertices more deeply. The next page covers endpoints, adjacency, and neighbors—the vocabulary for describing how vertices relate through edges.
You now understand the rigorous mathematical definition of graphs. This notation—G = (V, E)—is the universal language used in academic papers, algorithm specifications, and technical discussions. You can confidently interpret and use formal graph notation.