Topic 04 — CS 70 Discrete Mathematics
Graph
Theory
Graphs are the language of networks, relationships, and structure. From the internet to social networks to circuit design — everything is a graph. This guide builds graph theory from scratch with complete, rigorous proofs.
Graph Basics
A graph G = (V, E) consists of:
- V — a set of vertices (also called nodes)
- E — a set of edges, where each edge is an unordered pair {u, v} with u, v ∈ V
In this course, graphs are undirected (edges have no direction) and simple (no self-loops, no multiple edges between the same pair).
Undirected Graph
Edge {u,v} = {v,u}. No direction. Like a two-way road.
Directed Graph
Edge (u,v) ≠ (v,u). Has direction. Like a one-way road.
Simple Graph
No self-loops ({v,v}) and no multi-edges (at most one edge between any pair).
Weighted Graph
Each edge has a numerical weight. Used in shortest-path problems.
Incidence and Adjacency
An edge {u, v} is incident to both u and v. Two vertices are adjacent (or neighbors) if there is an edge between them. The neighborhood N(v) of vertex v is the set of all vertices adjacent to v.
Degree & The Handshaking Lemma
The degree of a vertex v, written deg(v), is the number of edges incident to v — equivalently, the number of neighbors of v.
For any graph G = (V, E):
The sum of all vertex degrees equals twice the number of edges.
Count edge-vertex incidences in two ways:
- Counting by vertices: Each vertex v contributes deg(v) incidences (one per incident edge). Total = ∑ deg(v).
- Counting by edges: Each edge {u,v} contributes exactly 2 incidences (one for u, one for v). Total = 2|E|.
Since both counts the same thing: ∑ deg(v) = 2|E|. ∎
The "handshake" analogy: in a room of handshakes, counting handshakes per person gives twice the number of handshakes (since each handshake involves two people).
Paths, Walks, and Connectivity
Walk: A sequence v₀, v₁, ..., vₖ where {vᵢ, vᵢ₊₁} ∈ E for all i. May repeat vertices and edges.
Path: A walk with no repeated vertices (and hence no repeated edges).
Cycle: A walk v₀, v₁, ..., vₖ = v₀ with no repeated vertices except start=end, with k ≥ 3.
Connected: u and v are connected if there is a path from u to v. A graph is connected if all pairs of vertices are connected.
Connected Component: A maximal connected subgraph — a largest subset of vertices that are all pairwise connected.
Bipartite Graphs
A graph G = (V, E) is bipartite if V can be partitioned into two disjoint sets L and R such that every edge goes between L and R. No edge connects two vertices in the same set.
A graph G is bipartite if and only if it contains no odd-length cycle.
Examples: Trees (always bipartite — no cycles at all), the complete bipartite graph Kₘ,ₙ (m vertices on left, n on right, all edges between sides), and any graph that can be 2-colored.
Eulerian Tours and Walks
Eulerian Tour: A closed walk (starts and ends at same vertex) that uses every edge exactly once. The graph must be connected.
Eulerian Walk: A walk (may start and end at different vertices) that uses every edge exactly once.
Eulerian Graph: A connected graph that has an Eulerian tour.
A connected graph has an Eulerian tour if and only if every vertex has even degree.
A connected graph has an Eulerian walk if and only if it has exactly 0 or 2 vertices of odd degree. (0 means the walk is a tour; 2 means the walk starts at one odd-degree vertex and ends at the other.)
If all vertices have even degree, then every time we enter a vertex (using one edge), we can exit using a different unused edge — unless we're at the start vertex and have used up all adjacent edges. So whenever we get stuck, we're at the start. The walk is closed.
For the 7-vertex graph in discussion: check vertex degrees. If all even → Eulerian tour exists. If exactly 2 odd-degree vertices → only Eulerian walk. If >2 odd-degree → neither.
The Königsberg Bridge Problem (1736): Euler proved no walk existed crossing each of 7 bridges exactly once. The four land masses had odd degree (3,3,3,5). Since >2 odd vertices, no Eulerian walk exists. This is often cited as the origin of graph theory.
Trees
A tree is a graph satisfying any of the following equivalent conditions:
- Connected and acyclic (no cycles)
- Connected with exactly |V| − 1 edges
- Connected where removing any single edge disconnects the graph
- Acyclic where adding any single edge creates a cycle
Trees are the "minimally connected" graphs — just enough edges to be connected, but none to spare.
Proving Tree Equivalences
The four definitions of a tree are all equivalent. The key tool is the degree-1 (leaf) lemma:
Any connected graph with |V| − 1 edges has at least one vertex of degree 1.
By handshaking, ∑ deg(v) = 2|E| = 2(|V|−1). Average degree = 2(|V|−1)/|V| = 2 − 2/|V| < 2. Since the average degree is strictly less than 2, not all vertices can have degree ≥ 2. So at least one vertex has degree ≤ 1. Since connected with |V| ≥ 2, degree 0 is impossible (isolated vertices can't be connected). So some vertex has degree exactly 1. ∎
By induction on n = |V|.
Base case (n=1): 1 vertex, 0 edges. Trivially acyclic. ✓
Inductive step: Assume true for graphs with n vertices. Consider a connected graph G with n+1 vertices and n edges. By the leaf lemma, G has a leaf — a vertex v of degree 1. Remove v and its edge. The remaining graph G' has n vertices and n−1 edges, and is still connected (v was degree 1, so removing it can't disconnect other vertices). By IH, G' is acyclic. Now, v had degree 1, so it is not part of any cycle. So G is acyclic. ∎
Tree Properties from Discussion
From the proof above, average degree = 2 − 2/n < 2. So at least one vertex has degree 1 (leaf). Now suppose only one leaf v exists. Remove v; G' = G − v has n−1 vertices and n−2 edges. G' is connected (since v was the only leaf). But a connected graph with n−1 vertices and n−2 edges has a leaf by our lemma, giving a second leaf in G' — and this leaf is also a leaf in G (removing degree-1 vertex doesn't change others' degrees). Contradiction with "only one leaf." ∎
Base case (n=2): One edge, two vertices. Bipartite (one in each part). ✓
IH: Any tree with n vertices is bipartite.
Step: Take a tree T on n+1 vertices. T has a leaf v (connected to exactly one neighbor u). Remove v; T' = T − v is a tree on n vertices. By IH, T' is bipartite with parts L and R. Place v in the opposite part from u: if u ∈ L, put v ∈ R (or vice versa). The only edge incident to v is {v, u}, which goes between parts. So T is bipartite. ∎
Degree Sequences (DIS 2A)
The degree sequence of a graph is the sorted (descending) list of all vertex degrees. Not every sequence corresponds to a valid graph.
- The sum of all degrees must be even (by Handshaking). If odd → impossible.
- Each degree must be in {0, 1, ..., n−1} where n = |V|. A degree of n or more is impossible in a simple graph.
- Degrees 0 and n−1 cannot coexist (degree n−1 means connected to all others, but degree 0 means connected to none — contradiction if both exist in same connected component).
(a) (3,3,2,2): Sum = 10 = 2×5. Four vertices. Max degree 3 = n−1 = 3 ✓. Valid! Draw: two vertices of degree 3 connected to each other and to both degree-2 vertices. Degree-2 vertices connected to both degree-3 vertices. Works.
(b) (3,2,2,2,2,1,1): Sum = 13. Odd! Impossible by handshaking.
(c) (6,2,2,2): 4 vertices. Max degree 6 but n−1 = 3. A vertex can have degree at most 3 in a 4-vertex simple graph. Impossible.
(d) (4,4,3,2,1): 5 vertices. Max degree 4 = n−1 ✓. Sum = 14 = 2×7 ✓. Valid! (Though constructing it takes care.)
Practice Problems
A graph has 7 edges. Three vertices have degree 3, two have degree 2, and the rest have degree 1. How many vertices does it have?
Solution: Sum = 3×3 + 2×2 + k×1 = 9+4+k = 2×7 = 14. So k = 1. Total vertices = 3+2+1 = 6.
Can you find an Eulerian tour on a graph where all 6 vertices have degree 4? Yes (all even degree, assuming connected). What about degree sequence (4,4,4,4,3,3)? No tour (two odd-degree vertices) but an Eulerian walk exists from one degree-3 vertex to the other.
A tree on 10 vertices has exactly 3 leaves. What is the sum of the internal vertex degrees? Internal vertices have degree ≥ 2. Sum of ALL degrees = 2×9 = 18. Leaf degrees sum = 3. Internal sum = 18−3 = 15.