Description
Pair up with another student to solve both problems below. Each of you is responsible for authoring
a (handwritten) solution to one of the problems. For example, if you author the solution to Problem
A, then your partner authors the B solution. Make sure you write your name as well as your partner’s
name in the upper-right corner of your solution, since both of you will receive points for each of the
solutions. You are only allowed to discuss the problems with your partner and the lab instructor.
Use of course notes, textbook, and lecture recordings is permitted, but no other online resources or
outside communication is allowed. Upload your solution in a single file to the appropriate drop box
before the end of class. Please show work and make sure you submit on time! Points will
be lost otherwise.
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)
