Description
Problems
A. By definition, a graph G = (V, E) is a pair of sets, where V is the vertex set, and E is the edge
set. For this problem we’ll assume that each vertex can be identified with a positive integer.
Moreover, recall that each edge of the graph may be represented as an ordered pair of the form
(u, v), where vertices u, v ∈ V .
1. Define a finite alphabet Σ so that every possible graph G = (V, E) may be encoded using
some word w over Σ. (10 pts)
2. Use Σ to provide an encoding word for the following graph. (5 pts)
1 2 3 7
4 5 6 8
1
B. Use strong mathematical induction to prove the following statement. “Let w ∈ {a, b}
∗ be a
word satisfying |w| ≥ 3, and for which w has more a’s than b’s. Then w must have one of the
following subwords: aaa, aab, aba, baa.” Hint: use a proof by cases for the inductive step. (15
pts)
2
