Introduction to Discrete Mathematics, Fall 2000
Problem Set 7, 7 - 9 November

1. Find some 16-bit binary De Bruijn sequence over the binary alphabet, i.e. a 16-character sequence $w \in \{0,1\}^{16}$ that, when read cyclically, contains all 4-character sequences $x \in \{0,1\}^{4}$ as subsequences.

2. 1. Draw pictures of all nonisomorphic 6-node trees.
   2. Prove that there are at least $e^{n-1}/n^3$ distinct isomorphism types of $n$-node trees. (Hint: Apply the Sylvester-Cayley tree counting theorem and the inequality $e(\frac{n}{e})^n \leq n! \leq ne(\frac{n}{e})^n$.)

3. Prove that a graph $G = (V,E)$ is a tree, if and only if it is acyclic, but inserting any one new edge into $G$ creates a cycle.

4. Prove the following claims:
   1. Every tree with at least two nodes contains at least two leaves.
   2. Let $G = (V,E)$ be an arbitrary graph, and $u \in V$ a leaf (= node of degree 1) in $G$ . Then $G$ is a tree, if and only if the graph $G-u$ (= the subgraph of $G$ spanned by nodes $V\setminus\{u\}$) is a tree.

5. Determine the Prüfer codes of the following trees (cf. Balakrishnan, pp. 168-169):
   
   What is the 7-node tree corresponding to the Prüfer code (3,1,4,1,5)?

6. A hypercube graph $H_n$ has as nodes all the $n$-bit binary sequences $u \in \{0,1\}^n$, and nodes $u$ and $v$ are connected by an edge if and only if the corresponding binary sequences differ in exactly one position.
   1. Draw pictures of the graphs $H_3$ and $H_4$. How many nodes are there in graph $H_n$?
   2. For which values of $n$ does $H_n$ contain a closed Eulerian tour?
   3. Determine the diameter of graph $H_n$, i.e. the biggest possible internode distance in $H_n$, $d(H_n) = \max \{d(u,v) \;\vert\; u, v \in H_n\}$, where the distance $d(u,v)$ between nodes $u, v \in H_n$ is defined as the length of the shortest path connecting them.

7. Prove, by induction on $n$, that every hypercube graph $H_n$, $n \geq 2$, contains a Hamiltonian cycle. (Hint: Assume inductively that graph $H_n$ contains a Hamiltonian path from node $u = 00\dots 0$ to node $v = 10\dots 0$. Observe that two such paths can be connected into a similar Hamiltonian path in $H_{n+1}$.) Draw pictures of the Hamiltonian paths based on this construction for the graphs $H_3$ and $H_4$.

   (Note: The Hamiltonian cycles of hypercube $H_n$ correspond to so called cyclic Gray codes of the integers 0, ..., $2^n-1$. These have the property that the binary representations of any two consequent numbers differ in exactly one bit.)