Difficulty: Intermediate | Prerequisites: Chapter 5 (induction), basic set theory
Tags: graph, vertex, edge, directed graph, undirected graph, simple graph, multigraph, pseudograph, adjacency list, adjacency matrix, degree, handshaking theorem, path, circuit, Euler circuit, connected graph, bipartite graph, complete graph, cycle, wheel, tree, rooted tree, binary tree, forest, relation, equivalence relation, equivalence class, partial order, transitive closure, CS182, discrete math, Purdue
Graphs model relationships between objects: social networks, computer networks, road maps, web links, dependency chains. Trees are a special type of graph that model hierarchies (file systems, org charts, decision trees). Relations generalise the idea of "connection" between elements of sets, giving you equivalence classes and partial orders. This material is fundamental to data structures, databases, networking, and compiler design. You should be comfortable with sets, functions, and induction before starting.
A graph is a set of vertices connected by edges. Directed graphs have one-way edges; undirected graphs have two-way edges. Key properties include degree, paths, circuits, and connectedness. Trees are connected graphs with no cycles. Relations on sets can be reflexive, symmetric, transitive, and more, leading to equivalence relations (which partition a set) and partial orders (which rank elements).
Graph (G = (V, E))
A structure consisting of a nonempty set V of vertices (nodes) and a set E of edges, where each edge connects one or two vertices.
Simple graph
A graph with no loops and no multiple edges between the same pair of vertices.
Multigraph
A graph that may have multiple edges between the same pair of vertices, but no loops.
Pseudograph
A graph that may have both loops and multiple edges.
Directed graph (digraph)
A graph where each edge has a direction: an ordered pair (u, v) meaning the edge goes from u to v.
Adjacent / Neighbours
Two vertices u and v are adjacent if an edge connects them.
Degree (deg(v))
The number of edges incident with vertex v. A loop contributes 2 to the degree.
In-degree (deg⁻(v))
In a directed graph, the number of edges terminating at v.
Out-degree (deg⁺(v))
In a directed graph, the number of edges starting at v.
Handshaking theorem
For an undirected graph with m edges: 2m = Σ deg(v) over all vertices v. In simple terms, the sum of all vertex degrees equals twice the number of edges.
Path
A sequence of edges travelling from vertex to vertex. In a simple graph, described by the vertex sequence x₀, x₁, ..., xₖ.
Circuit (cycle)
A path that begins and ends at the same vertex.
Simple path / simple circuit
A path or circuit that does not repeat any edge.
Connected graph
An undirected graph where there is a path between every pair of vertices.
Connected component
A maximal connected subgraph.
Euler circuit
A simple circuit that contains every edge of the graph exactly once.
Complete graph (Kₙ)
The simple graph on n vertices with exactly one edge between every pair. It has C(n, 2) edges.
Cycle (Cₙ)
A graph on n >= 3 vertices arranged in a ring, each connected to its two neighbours.
Wheel (Wₙ)
A cycle Cₙ with one additional central vertex connected to every vertex in the cycle.
Bipartite graph
A graph whose vertices can be split into two disjoint sets V₁ and V₂ such that every edge connects a vertex in V₁ to one in V₂. Equivalently, it can be 2-coloured so no two adjacent vertices share a colour.
Tree
A connected, undirected graph with no simple circuits.
Forest
A graph with no simple circuits (not necessarily connected). Each connected component is a tree.
Rooted tree
A tree with one designated root vertex, with edges directed away from the root. Terminology: parent, child, sibling, leaf, internal vertex, level, height.
M-ary tree
A rooted tree where every internal vertex has at most m children. Full m-ary: every internal vertex has exactly m children. Binary tree: m = 2.
Binary relation
A relation R on sets A and B is a subset of A × B. aRb means (a, b) ∈ R.
Reflexive
For all a ∈ S, aRa. Every element is related to itself.
Symmetric
If aRb then bRa.
Antisymmetric
If aRb and bRa then a = b.
Transitive
If aRb and bRc then aRc.
Equivalence relation
A relation that is reflexive, symmetric, and transitive. It partitions the set into equivalence classes.
Equivalence class
The set of all elements equivalent to a given element under an equivalence relation.
Partial order
A relation that is reflexive, antisymmetric, and transitive (e.g. <=, ⊆).
Transitive closure
The smallest transitive relation containing R. Computed using Warshall's algorithm in O(n³).
A graph G = (V, E) has vertices and edges. Edges can be undirected (unordered pairs) or directed (ordered pairs).
Graph types:
Simple graph: no loops, no multiple edges
Multigraph: multiple edges allowed, no loops
Pseudograph: loops and multiple edges allowed
Directed graph: edges have direction
Applications of graphs:
Social networks (friend graphs, collaboration graphs)
Communication networks (cell graphs)
Information networks (web graphs, citation graphs)
Software design (module dependency)
Transportation (airline routes, road networks)
deg(v) = number of edges incident with v (loops count twice)
Handshaking theorem: 2m = Σ deg(v). Consequence: the number of vertices with odd degree is even.
Example: 10 vertices, each of degree 6. Then 2m = 60, so m = 30 edges.
Example: can a graph with 5 vertices have every vertex of degree 3? Sum = 15, which is odd, so no.
Directed graphs: |E| = Σ deg⁻(v) = Σ deg⁺(v).
Complete graph Kₙ: one edge between every pair. C(n, 2) edges.
Cycle Cₙ (n >= 3): a single ring of n vertices.
Wheel Wₙ: Cₙ plus a hub connected to all n vertices.
Network topologies: star (all connected to one hub), ring (Cₙ), wheel (Wₙ), mesh (Kₙ or grid).
A graph is bipartite if and only if it contains no odd-length cycles. Equivalently, its vertices can be 2-coloured.
Adjacency list: for each vertex, list its neighbours. Space-efficient for sparse graphs.
Adjacency matrix: an n × n matrix where entry (i, j) is 1 if vertices i and j are adjacent, 0 otherwise. For simple undirected graphs, the matrix is symmetric with zeros on the diagonal.
Sparse graphs (few edges relative to n²): adjacency list is more efficient.
Dense graphs: adjacency matrix may be preferable for constant-time edge lookups.
A path is simple if no edge is repeated.
A circuit starts and ends at the same vertex.
A graph is connected if every pair of vertices has a path between them.
Connected components are maximal connected subgraphs.
Degrees of separation: the shortest path between two people in a social network. The "six degrees of separation" conjecture says most people are linked by chains of at most six. Erdős numbers and Bacon numbers are examples.
Shortest paths on a grid: on a 9×9 grid, the number of shortest paths from corner A to corner B (moving only right and down) is C(16, 8) (choose 8 of 16 steps to be rightward).
An Euler circuit visits every edge exactly once and returns to the start.
Necessary and sufficient condition: a connected graph has an Euler circuit if and only if every vertex has even degree.
Historical note: Euler proved this for the Seven Bridges of Königsberg, founding graph theory.
A tree is a connected undirected graph with no simple circuits.
Theorem: a tree with n vertices has exactly n - 1 edges.
A forest is a graph with no circuits; each component is a tree.
One vertex is the root; edges are directed away from it.
Parent: the vertex one step closer to the root. Children: vertices one step farther.
Leaf: a vertex with no children. Internal vertex: a vertex with at least one child.
Level: distance from the root. Height: maximum level of any vertex.
Full m-ary: every internal vertex has exactly m children.
Binary tree (m = 2): every internal vertex has a left child and a right child.
Full binary tree vertex bound: n(T) <= 2^(h(T)+1) - 1.
A relation R from A to B is a subset of A × B. A relation on A is a subset of A × A.
Properties:
Reflexive: aRa for all a (diagonal is all 1s in the matrix)
Irreflexive: aRa never holds
Symmetric: aRb implies bRa (matrix is symmetric)
Antisymmetric: aRb and bRa implies a = b
Transitive: aRb and bRc implies aRc
Examples on spatial lines: parallel is reflexive, symmetric, transitive. Perpendicular is irreflexive, symmetric.
Examples on graph vertices: adjacency in undirected graphs is irreflexive and symmetric. Connectedness is reflexive, symmetric, and transitive.
Matrix: an n × n matrix M_R where m_{ij} = 1 if a_i R a_j.
Directed graph: vertices are elements, edge from a to b if aRb.
If R is a relation on A × B and S is on B × C, the composite S ∘ R consists of all (a, c) where there exists b with aRb and bSc.
R is "parent": R² = R ∘ R is "grandparent."
R is "adjacent": R³ is "connected by a path of length 3."
R is transitive if and only if Rⁿ ⊆ R for all n.
The transitive closure of R is a graph with the same vertices and an edge from a to b whenever G contains a path from a to b.
Computed by Warshall's algorithm in O(n³).
Using matrices: the matrix of paths of length k or less is M ∨ M² ∨ ... ∨ Mᵏ (with ∨ applied element-wise).
An equivalence relation is reflexive, symmetric, and transitive. It partitions its domain into equivalence classes.
Congruence mod m: partitions Z into m classes {0, m, 2m, ...}, {1, m+1, 2m+1, ...}, ..., {m-1, 2m-1, ...}.
Strings whose first k characters are equal: partitions strings by their k-length prefix.
Class representatives: one element per class (e.g. 0, 1, ..., m-1 for congruence mod m).
A partial order is reflexive, antisymmetric, and transitive. A linear (total) order adds: for all a, b, either aRb or bRa.
Examples: <=, >=, ⊆, ⊇ are partial orders. <= and >= on integers are linear orders. ⊆ on sets is not (some sets are incomparable).
A strict partial order is irreflexive, antisymmetric, and transitive (e.g. <, >, ⊂).
A linear order on strings: compare character by character from left to right. If the first k-1 characters match and the k-th differs, the string with the smaller k-th character comes first. A shorter string that is a prefix of a longer one comes first.
Handshaking theorem: 2m = Σ deg(v)
Complete graph edges: |E(Kₙ)| = C(n, 2) = n(n-1)/2
Tree edges: n vertices implies n - 1 edges
Full binary tree: n(T) <= 2^(h(T)+1) - 1
Directed graph degree sum: |E| = Σ deg⁻(v) = Σ deg⁺(v)
Graphs model the internet (web graph), social networks (Facebook's friend graph has billions of vertices), and transportation systems. Trees model file systems, HTML document structure, and decision processes. Equivalence relations appear in databases (grouping records by a key) and in modular arithmetic. Partial orders model task scheduling (some tasks must precede others, but some are independent).
"Every graph is simple." Many real-world graphs have loops or multiple edges. Always check which type of graph a problem specifies.
"A tree can have cycles." By definition, a tree has no simple circuits. If it has a cycle, it is not a tree.
"Euler circuit and Hamiltonian circuit are the same." An Euler circuit visits every edge once; a Hamiltonian circuit visits every vertex once. Different problems, different conditions.
"Antisymmetric means not symmetric." They are independent properties. A relation can be both symmetric and antisymmetric (e.g. equality), or neither.
⚠️ Use the handshaking theorem to check whether a proposed degree sequence is possible.
⚠️ Know the Euler circuit condition: every vertex must have even degree.
⚠️ Be able to write adjacency matrices and adjacency lists for given graphs.
⚠️ Know the difference between reflexive/irreflexive, symmetric/antisymmetric.
⚠️ Be able to determine whether a relation is an equivalence relation or a partial order.
⚠️ For trees: n vertices means n - 1 edges. This is a frequently tested fact.
Fill in the blank: A tree with 20 vertices has ______ edges.
True or False: The adjacency matrix of a simple undirected graph is symmetric.
Fill in the blank: K₅ has ______ edges.
True or False: An equivalence relation must be antisymmetric.
Fill in the blank: An Euler circuit exists if and only if every vertex has ______ degree.
Answers: 1. 19. 2. True. 3. C(5,2) = 10. 4. False (it must be symmetric). 5. even.
Q: A graph has 10 vertices, each of degree 4. How many edges does it have?
A: By the handshaking theorem, 2m = 10 × 4 = 40, so m = 20.
Q: Is the "less than" relation (<) on integers an equivalence relation?
A: No. It is irreflexive (a < a is false) and not symmetric (a < b does not imply b < a). It is a strict partial order.
Q: Can a graph with 7 vertices where each has degree 3 exist?
A: Sum of degrees = 21, which is odd. By the handshaking theorem, 2m must be even. Contradiction, so no.
Q: What are the equivalence classes of congruence mod 3 on the integers?
A: Three classes: {0, 3, 6, 9, ...}, {1, 4, 7, 10, ...}, {2, 5, 8, 11, ...}. (Including negative integers in each class.)
Graphs connect to algorithms (Chapter 3) through graph traversal algorithms (BFS, DFS) and shortest-path algorithms. Trees connect to induction (Chapter 5) through structural induction proofs. Relations connect to number theory (Chapter 4) through congruence mod m, which is an equivalence relation. Bipartite graphs connect to matching problems in later courses.
graph theory, vertex, node, edge, arc, directed graph, digraph, undirected graph, simple graph, multigraph, pseudograph, loop, adjacent, neighbour, neighbourhood, degree, in-degree, out-degree, handshaking theorem, path, circuit, cycle, Euler circuit, Euler path, Königsberg bridges, connected, disconnected, connected component, tree, forest, rooted tree, binary tree, m-ary tree, leaf, internal vertex, height, level, complete graph, cycle graph, wheel graph, bipartite, 2-colourable, adjacency matrix, adjacency list, relation, reflexive, symmetric, antisymmetric, transitive, equivalence relation, equivalence class, partition, partial order, linear order, total order, strict partial order, lexicographic order, transitive closure, Warshall's algorithm, composition of relations, CS 182, Purdue, discrete math