Introduction to Graph Theory

Learning Objectives

• Define a graph in terms of vertices and edges, and distinguish directed, undirected, and weighted graphs.
• Represent a graph using an adjacency matrix and an adjacency list, and compare their trade-offs.
• Trace Depth-First Search (DFS) and Breadth-First Search (BFS) by hand on a small graph.
• Identify key graph properties: connectedness, cycles, and bipartiteness.
• Explain how graph algorithms power real systems such as maps, social networks, and search engines.
• Analyze the time and space cost of basic graph operations under each representation.

Quick Answer

A graph is a mathematical structure made of vertices (points, also called nodes) connected by edges (links between points). It's the most natural way to model relationships: cities connected by roads, people connected by friendships, web pages connected by hyperlinks, or tasks connected by dependencies. Graph theory matters because an enormous share of real-world computing problems — routing (GPS), ranking (search engines), scheduling (task dependencies), and clustering (social networks) — are really graph problems wearing a different name. Once you can recognize "this is a graph problem," decades of well-studied algorithms like DFS, BFS, Dijkstra's, and PageRank become available to solve it efficiently.

What Is a Graph?

Formally, a graph G = (V, E) consists of:

• V, a set of vertices (also called nodes) — the entities being modeled.
• E, a set of edges — the connections between pairs of vertices.

This definition leans directly on set theory: V and E are just sets, and an edge is (in the undirected case) a 2-element subset of V, or (in the directed case) an ordered pair.

Real-world example: A city's road network is a graph — intersections are vertices, roads are edges. Your phone's maps app runs shortest-path algorithms over exactly this graph every time it plans a route.

Why it matters: Graphs let us reuse the same handful of algorithms (DFS, BFS, shortest path, spanning tree) across wildly different domains, because the structure of "things connected to other things" is identical whether the things are cities, web pages, or people.

Common misunderstanding: Students often think a graph must "look like" a drawing with crossing lines. The visual layout is irrelevant — two drawings that connect the same vertices the same way are the same graph, even if one looks tangled and the other looks neat. What matters is only which pairs of vertices are joined.

Types of Graphs

Type	Description	Example
Undirected	Edges have no direction; (A,B) means A and B are connected both ways	Facebook friendship
Directed (digraph)	Edges have a direction, from one vertex to another	Twitter "follows"
Weighted	Each edge carries a numerical cost or distance	Road network with distances
Unweighted	All edges are treated as equal cost	A simple friendship graph

Key Terminology

• Adjacent: Two vertices connected directly by an edge.
• Incident: An edge is incident to the vertices it connects.
• Degree: The number of edges touching a vertex (in directed graphs, split into in-degree and out-degree).
• Path: A sequence of edges connecting a sequence of distinct vertices.
• Cycle: A path that starts and ends at the same vertex.
• Connected graph: A graph where a path exists between every pair of vertices.
• Bipartite graph: A graph whose vertices can be split into two disjoint groups such that every edge joins a vertex in one group to a vertex in the other (no edges within a group).

Graph Representations

How you store a graph in memory determines how fast your algorithms run — this is the single most important practical decision in graph programming.

Adjacency Matrix

A |V| × |V| grid where cell (i, j) = 1 if an edge connects vertex i and vertex j, else 0.

$$\text{Graph: A–B, B–C, A–C} \quad \begin{array}{c|ccc} & A & B & C \\ \hline A & 0 & 1 & 1 \\ B & 1 & 0 & 1 \\ C & 1 & 1 & 0 \end{array}$$

• Checking if an edge exists: O(1) — just look up the cell.
• Space used: O(V²) — even if the graph has very few edges.

Adjacency List

Each vertex stores a list of its neighbors.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

• Checking if an edge exists: O(degree of vertex) — must scan the neighbor list.
• Space used: O(V + E) — proportional to the actual number of edges, not the square of vertex count.

Worked example — adding and removing structure: Start from the adjacency list above.

# Add a new isolated vertex 'D'
graph['D'] = []

# Add an edge between 'A' and 'D'
graph['A'].append('D')
graph['D'].append('A')

# Remove vertex 'B' and every edge that touched it
def remove_vertex(graph, vertex):
    if vertex in graph:
        del graph[vertex]
        for v in graph:
            if vertex in graph[v]:
                graph[v].remove(vertex)

remove_vertex(graph, 'B')
print(graph)
# {'A': ['C', 'D'], 'C': ['A'], 'D': ['A']}

Tracing this by hand: after adding D, A → [B, C, D] and D → [A]. Removing B deletes the 'B' key entirely, then scans every remaining vertex's list and strips out 'B' — this scan is what makes vertex removal O(V + E) in an adjacency list, versus a cheaper O(V) row/column clear in an adjacency matrix.

Why it matters: A social network with a billion users but a few hundred friends each is sparse — an adjacency list uses a fraction of the memory an adjacency matrix would need (O(V+E) vs O(V²)). A densely connected small graph (like a fully-meshed server cluster) may favor the matrix for its O(1) edge lookups.

Common misunderstanding: Students often assume the adjacency matrix is always "better" because lookups are O(1). For sparse real-world graphs (most graphs found in practice — social networks, road maps, the web), the matrix wastes enormous memory storing mostly zeros; the list representation almost always wins outside of dense, small graphs.

Graph Traversal

Traversal algorithms visit every reachable vertex from a starting point — the foundation for search, connectivity checks, and pathfinding.

Depth-First Search (DFS)

DFS commits to one branch, following it as far as possible before backtracking.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(graph, 'A')

Trace by hand on A: [B, C], B: [A, C], C: [A, B], starting at A:

1. Visit A, mark visited = {A}. Print A.
2. Look at A's neighbors: B (unvisited) → recurse into B.
3. Visit B, mark visited = {A, B}. Print B.
4. B's neighbors: A (visited, skip), C (unvisited) → recurse into C.
5. Visit C, mark visited = {A, B, C}. Print C.
6. C's neighbors: A (visited), B (visited) — nothing left, backtrack all the way out.

Output order: A, B, C.

Breadth-First Search (BFS)

BFS explores all neighbors at the current distance before moving one level further out, using a queue instead of recursion.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            queue.extend([n for n in graph[vertex] if n not in visited])

bfs(graph, 'A')

Why it matters: DFS naturally suits problems like maze-solving, topological sorting, and detecting cycles. BFS naturally suits shortest-path-in-unweighted-graphs problems, like "fewest number of hops between two users" in a social network — because BFS always finds a target at its true minimum distance first.

Common misunderstanding: Students often think DFS and BFS will always visit vertices in the same order, or that one is strictly "better." Neither is true — the correct choice depends entirely on what you're trying to find. Use BFS when you need shortest paths in an unweighted graph; use DFS when you need to explore full paths, detect cycles, or when memory for a queue would be prohibitive (DFS's recursion stack is typically shallower than BFS's queue on wide graphs).

Applications of Graph Theory

1. Shortest Path Algorithms — Dijkstra's and Bellman-Ford compute the cheapest route between vertices, powering GPS navigation.
2. Network Flow — Ford-Fulkerson calculates maximum flow through a network, used in bandwidth allocation and bipartite matching.
3. Graph Coloring — Assigns labels ("colors") so adjacent vertices differ, used in exam/timetable scheduling and register allocation in compilers.
4. Social Network Analysis — Detects friend clusters, influencers, and shortest "degrees of separation" paths.
5. Web Search — PageRank models the web as a directed graph and ranks pages by how the graph's link structure votes for them.

Diagram: Graph Theory Concept Map

Key Terms

Term	Definition
Vertex (node)	A basic entity in a graph.
Edge	A connection between two vertices, directed or undirected, weighted or not.
Degree	Number of edges incident to a vertex.
Adjacency matrix	A |V|×|V| table marking which vertex pairs are connected.
Adjacency list	A per-vertex list of neighboring vertices.
Path	A sequence of edges linking a chain of distinct vertices.
Cycle	A path that returns to its starting vertex.
Connected graph	A graph in which every vertex is reachable from every other vertex.
Bipartite graph	A graph whose vertices split into two groups with edges only crossing between groups, never within one.
DFS / BFS	Depth-First Search / Breadth-First Search — the two fundamental traversal strategies.

Common Mistakes

Misconception 1: "A denser drawing means a more complex graph." Why it's wrong: Visual layout has nothing to do with graph structure — the same graph can be drawn as a tangled mess or a tidy diagram. Correct explanation: Complexity is measured by |V| and |E| (and properties like degree distribution), not by how the picture looks. Always check the vertex/edge sets, not the drawing.

Misconception 2: "Adjacency matrices are always faster because lookups are O(1)." Why it's wrong: O(1) lookup ignores the O(V²) memory cost, which becomes catastrophic for large sparse graphs (e.g., a billion-user social graph would need an astronomically large matrix). Correct explanation: Choose the representation based on density. For sparse graphs (E is much smaller than V²), an adjacency list's O(V+E) space usually wins overall, even though single-edge lookups are slower.

Misconception 3: "DFS and BFS always find the same path." Why it's wrong: They explore vertices in fundamentally different orders (depth-first vs. level-by-level), so the paths they discover first can differ, especially in graphs with multiple valid paths. Correct explanation: Only BFS is guaranteed to find the shortest path in an unweighted graph, because it finishes exploring all vertices at distance k before considering any vertex at distance k+1. DFS makes no such guarantee.

Comparison and Connections

Aspect	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Edge existence check	O(1)	O(degree)
Best for	Dense graphs, frequent edge queries	Sparse graphs, most real-world graphs
Iterating all neighbors	O(V) even if few neighbors	O(degree) — only real neighbors

Aspect	DFS	BFS
Data structure	Stack / recursion	Queue
Explores	Deep paths first	Level by level (nearest first)
Shortest path (unweighted)	Not guaranteed	Guaranteed
Typical use	Cycle detection, topological sort, maze solving	Shortest hop count, level-order tasks
Memory pattern	Can be shallow on narrow graphs	Can be wide on bushy graphs

Practice Questions

Recall 1. Give the formal definition of a graph G = (V, E). Answer guidance: A graph is a pair of sets: V, the vertices, and E, the edges, where each edge connects two vertices (as an unordered pair for undirected graphs or an ordered pair for directed graphs).

Recall 2. Name the two standard ways to represent a graph in a program and state the space complexity of each. Answer guidance: Adjacency matrix, O(V²); adjacency list, O(V + E).

Understanding 1. Explain why BFS, but not DFS, guarantees the shortest path in an unweighted graph. Answer guidance: BFS explores all vertices at distance 1 before any at distance 2, and so on — so the first time it reaches the target, it must be via the shortest number of hops. DFS follows one path deep and may reach the target through a longer route first.

Understanding 2. Why is an adjacency list usually preferred for a graph representing a social network with millions of users? Answer guidance: Social networks are sparse — each user has hundreds of friends, not millions — so an adjacency matrix's O(V²) storage would be wasted almost entirely on zero entries. The adjacency list only stores real connections, giving O(V+E) space.

Application 1. You are given a directed graph of task dependencies (edge A→B means "A must finish before B starts"). Which traversal algorithm would you use to detect whether the dependencies contain a cycle (an impossible schedule), and why? Answer guidance: DFS — tracking a vertex's recursion-stack membership lets you detect a "back edge" (an edge pointing to a vertex already on the current DFS path), which indicates a cycle.

Application 2. A ride-share app models cities as vertices and roads as weighted edges (drive time). Which algorithm class should it use to compute the fastest route, and why not plain BFS? Answer guidance: Shortest-path algorithms for weighted graphs, like Dijkstra's algorithm. Plain BFS assumes every edge has equal cost (1 hop = 1 unit), so it cannot account for roads with different drive times; it would return the route with the fewest roads, not the fastest one.

Analysis 1. Compare, for a graph with 10,000 vertices and only 20,000 edges, the memory used by an adjacency matrix versus an adjacency list. Which would you pick, and why? Answer guidance: Matrix: about 10,000² = 100,000,000 cells. List: proportional to V + E ≈ 30,000 entries. The list is roughly 3,000x smaller here — clearly preferable for this sparse graph.

Analysis 2. A graph is bipartite. What does this tell you about its potential to contain an odd-length cycle, and why? Answer guidance: A bipartite graph cannot contain any odd-length cycle. Because every edge crosses between the two groups, any cycle must alternate group A → group B → group A → ... to return to its start, which forces the cycle length to be even.

FAQ

What's the difference between a path and a cycle? A path visits a sequence of distinct vertices connected by edges and does not return to its start. A cycle is a path that does return to its starting vertex, forming a closed loop.

Can a graph have edges with no vertices assigned, or vertices with no edges? A vertex with no edges (an isolated vertex) is perfectly valid — it's just a disconnected point. An edge always needs two endpoint vertices, so an "edge with no vertices" isn't a valid edge.

Why do directed graphs matter separately from undirected ones? Direction changes what "connected" means. A Twitter "follows" relationship is directional (you can follow someone who doesn't follow back), while a Facebook "friend" relationship is symmetric — modeling the wrong type misrepresents the real relationship entirely.

Is a tree a type of graph? Yes — a tree is a connected, undirected graph with no cycles. Every tree is a graph, but not every graph is a tree (graphs can have cycles and can be disconnected).

How do search engines like Google use graph theory? Google's PageRank models the web as a directed graph where pages are vertices and hyperlinks are directed edges. A page's importance is estimated from how many (and how important) other pages link to it — fundamentally a graph-theoretic computation.

Quick Revision

• A graph G = (V, E) is a set of vertices and a set of edges connecting them.
• Undirected edges go both ways; directed edges (digraphs) point one way; weighted edges carry a cost.
• Adjacency matrix: O(V²) space, O(1) edge lookup — good for dense graphs.
• Adjacency list: O(V+E) space, O(degree) edge lookup — good for sparse, real-world graphs.
• DFS uses a stack/recursion and explores deep before backtracking.
• BFS uses a queue and explores level by level — the only one that guarantees shortest paths in unweighted graphs.
• Degree = number of edges touching a vertex; a connected graph has a path between every pair of vertices.
• A cycle returns to its starting vertex; a bipartite graph can never contain an odd-length cycle.
• Shortest-path algorithms for weighted graphs (Dijkstra's, Bellman-Ford) generalize BFS to handle edge costs.
• Graph coloring solves scheduling and register-allocation problems by avoiding same-color adjacent vertices.
• PageRank and social network analysis treat the web/social graph as a directed graph to rank importance and detect clusters.
• Most real-world graphs are sparse (E ≪ V²), which is why adjacency lists dominate in practice.

Related Topics

Prerequisites: Sets and Propositions (a graph is defined from two sets), basic recursion (used in DFS), basic data structures (stacks and queues, used in DFS/BFS).

Related Topics: Trees and Graphs (Data Structures unit), Boolean Algebra (used in some graph-coloring constraint formulations), Network Layer and Routing Protocols (real-world shortest-path use).

Next Topics: Automata Theory (finite-state machines are directed graphs with labeled transitions), Dynamic Programming (many shortest-path and optimization algorithms on graphs use DP techniques).