## 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