Topic 06 — CS 70 Discrete Mathematics
Hypercubes &
Graph Types
From the densest graphs (complete graphs) to elegant bit-string structures (hypercubes). We prove the remarkable large-cut theorem: to disconnect even a small set of hypercube vertices, you must cut at least that many edges.
Complete Graphs
The complete graph Kₙ has n vertices and contains an edge between every pair of distinct vertices. It is the densest possible simple graph on n vertices.
Kₙ has exactly n(n−1)/2 edges.
Each vertex is adjacent to all n−1 others, so each has degree n−1. Sum of degrees = n(n−1). By Handshaking, |E| = n(n−1)/2. ∎
| Graph | Vertices | Edges | Avg Degree | Notes |
|---|---|---|---|---|
| K₃ | 3 | 3 | 2 | Triangle. Planar. |
| K₄ | 4 | 6 | 3 | Planar. |
| K₅ | 5 | 10 | 4 | NOT planar! |
| K₆ | 6 | 15 | 5 | NOT planar. |
| K₁₀ | 10 | 45 | 9 | NOT planar. |
Comparing Graph Families
Trees
|V|−1 edges. Sparsest connected graphs. Falls apart if any edge removed. Used for: spanning structures, hierarchies.
Complete Graphs Kₙ
n(n−1)/2 edges. Densest graphs. Very robust — many paths between any pair. Very expensive in edges.
Hypercubes Qₙ
n·2ⁿ⁻¹ edges. Middle ground — very connected (robust cuts), beautiful structure, represents bit strings.
The hypercube achieves an elegant balance: O(n log n) edges (vs O(n²) for complete), yet is highly robust — removing any small set of edges barely disconnects it.
The n-Dimensional Hypercube
The n-dimensional hypercube Qₙ = (V, E) is defined as:
- Vertices: V = {0,1}ⁿ — the set of all n-bit binary strings. There are 2ⁿ vertices.
- Edges: Two vertices are connected by an edge if and only if they differ in exactly one bit position.
Hypercube Structure & Counting
The n-dimensional hypercube Qₙ has:
- 2ⁿ vertices (one per n-bit string)
- n · 2ⁿ⁻¹ edges
- Each vertex has degree n (n neighbors: flip each of the n bits)
Each vertex has degree n (n neighbors, one per bit position). Sum of degrees = n · 2ⁿ. By Handshaking, |E| = n · 2ⁿ / 2 = n · 2ⁿ⁻¹. ∎
| Dimension n | Vertices 2ⁿ | Edges n·2ⁿ⁻¹ | Degree n |
|---|---|---|---|
| 1 | 2 | 1 | 1 |
| 2 | 4 | 4 | 2 |
| 3 | 8 | 12 | 3 |
| 4 | 16 | 32 | 4 |
| n | 2ⁿ | n·2ⁿ⁻¹ | n |
Recursive Construction
Base: Q₀ is a single vertex labeled with the empty string (0 bits).
Step: Qₙ is constructed from two copies of Qₙ₋₁:
- The 0-subcube: a copy of Qₙ₋₁ with all vertices prefixed by 0 (i.e., 0x for x ∈ {0,1}ⁿ⁻¹)
- The 1-subcube: a copy of Qₙ₋₁ with all vertices prefixed by 1 (i.e., 1x for x ∈ {0,1}ⁿ⁻¹)
- Plus the cross edges: connect each 0x in the 0-subcube to its corresponding 1x in the 1-subcube
0-subcube: {000, 001, 010, 011} (all edges of Q₂ with 0 prepended)
1-subcube: {100, 101, 110, 111} (all edges of Q₂ with 1 prepended)
Cross edges: 000↔100, 001↔101, 010↔110, 011↔111
Total edges: 4 (in 0-subcube) + 4 (in 1-subcube) + 4 (cross) = 12 = 3·2² ✓
Key Properties of Hypercubes
For any n ≥ 1, the n-dimensional hypercube Qₙ is bipartite.
Partition vertices by parity of the number of 1-bits:
- L = vertices with an even number of 1-bits (even parity)
- R = vertices with an odd number of 1-bits (odd parity)
Every edge connects two vertices that differ in exactly one bit. Flipping one bit changes the count of 1-bits by ±1, which changes parity (even↔odd). So every edge goes between L and R. Therefore Qₙ is bipartite. ∎
The edges of Qₙ can be colored with n colors such that no two edges sharing a vertex have the same color.
Color each edge by the bit position in which its two endpoints differ. Since Qₙ has edges only between vertices differing in one bit, each edge has a well-defined bit position (1 through n) — this is its color.
Two edges sharing a vertex: they differ from the same vertex in two different bit positions (otherwise they'd be the same edge). So they have different colors. ∎
The Large Cut Theorem
Given a graph G = (V, E) and a subset S ⊆ V:
- The cut (S, V−S) is the partition of vertices into S and its complement.
- The cut edges are E ∩ (S × (V−S)) — edges with one endpoint in S and one in V−S.
- The "small side" of a cut is the smaller of S and V−S.
For any cut (S, V−S) in the n-dimensional hypercube Qₙ where |S| ≤ |V|/2 = 2ⁿ⁻¹, the number of cut edges is at least |S|.
In other words: to disconnect a set of k vertices from the rest, you must cut at least k edges. This makes the hypercube extremely robust against edge removal.
Proof of the Large Cut Theorem
Base Case (n = 1): Q₁ has vertices {0, 1} and one edge {0,1}. Possible cuts: S = ∅ (0 edges ≥ 0) or S = {0} or S = {1} (1 cut edge ≥ 1 = |S|). ✓
Inductive Hypothesis: The theorem holds for Qₙ₋₁ (any cut in Qₙ₋₁ has ≥ |small side| cut edges).
Inductive Step: Consider Qₙ and any cut (S, V−S) with |S| ≤ 2ⁿ⁻¹. Use the recursive structure: Qₙ = 0-subcube ∪ 1-subcube ∪ cross edges. Write:
- S₀ = S ∩ (0-subcube) — part of S in 0-subcube
- S₁ = S ∩ (1-subcube) — part of S in 1-subcube
- |S₀| + |S₁| = |S|
Case 1: |S₀| ≤ 2ⁿ⁻² AND |S₁| ≤ 2ⁿ⁻² (both small within their subcubes)
Apply IH to 0-subcube: cut edges in 0-subcube ≥ |S₀|.
Apply IH to 1-subcube: cut edges in 1-subcube ≥ |S₁|.
Total cut edges ≥ |S₀| + |S₁| = |S|. ✓
Case 2: |S₀| ≥ 2ⁿ⁻² (S₀ is a "large" part of 0-subcube)
Since |S| ≤ 2ⁿ⁻¹ and |S₀| + |S₁| = |S|, we have |S₁| ≤ 2ⁿ⁻¹ − |S₀| ≤ 2ⁿ⁻². So S₁ is small within the 1-subcube.
- Edges in 1-subcube: |S₁| ≤ 2ⁿ⁻², so S₁ is the small side. By IH: cut edges in 1-subcube ≥ |S₁|.
- Edges in 0-subcube: |S₀| ≥ 2ⁿ⁻², so V₀ − S₀ is the small side (|V₀−S₀| = 2ⁿ⁻¹ − |S₀| ≤ 2ⁿ⁻²). By IH: cut edges in 0-subcube ≥ |V₀ − S₀| = 2ⁿ⁻¹ − |S₀|.
- Cross edges: The cross edges connect 0x ↔ 1x. A cross edge {0x, 1x} is a cut edge iff exactly one of {0x, 1x} is in S. If 0x ∈ S₀ and 1x ∉ S₁, that's |S₀| − |S₁| cross cut edges (those in S₀ with no matching S₁ partner). So: cross cut edges ≥ |S₀| − |S₁|.
- Total: cut edges ≥ |S₁| + (2ⁿ⁻¹ − |S₀|) + (|S₀| − |S₁|) = 2ⁿ⁻¹ = |V|/2 ≥ |S|. ✓
Case 3 (|S₁| ≥ 2ⁿ⁻²) is symmetric to Case 2. ∎
Hypercubes and Boolean Functions
The hypercube has deep connections to computer science. The vertices of Qₙ are exactly the 2ⁿ possible input strings to a Boolean function f: {0,1}ⁿ → {0,1}.
The cut edges of a subset S = f⁻¹(1) (inputs where f outputs 1) are exactly the pairs of inputs where flipping one bit changes the output — these are the "sensitive" or "border" inputs of f.
The Large Cut Theorem says: if a Boolean function outputs 1 on at most half the inputs, then there are at least that many input pairs where changing one bit changes the output. This is a form of robustness — a function cannot be "too concentrated" without having sensitive inputs.
Practice Problems (DIS 2B)
"How many edges need to be removed from a 3-dimensional hypercube to get a spanning tree?"
Q₃ has 8 vertices and 12 edges. A spanning tree on 8 vertices has 8−1 = 7 edges. Remove 12 − 7 = 5 edges.
Draw Q₁, Q₂, Q₃ with vertex labels.
Q₁: two vertices 0, 1 with one edge.
Q₂: four vertices 00, 01, 10, 11. Edges: 00-01, 00-10, 01-11, 10-11 (a 4-cycle/square).
Q₃: eight vertices. Each Q₂ vertex with 0 or 1 prepended, plus 4 cross edges.
In Q₂, let S = {00, 01} (|S| = 2 = |V|/2). Cut edges: 00-10 and 01-11. Count = 2 = |S|. ✓ (equality holds)
Now S = {00} (|S| = 1). Cut edges: 00-01 and 00-10. Count = 2 ≥ 1 = |S|. ✓ (strict inequality)