## 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 that, when read cyclically, contains all 4-character sequences as subsequences.

1. Draw pictures of all nonisomorphic 6-node trees.
2. Prove that there are at least distinct isomorphism types of -node trees. (Hint: Apply the Sylvester-Cayley tree counting theorem and the inequality .)

2. Prove that a graph is a tree, if and only if it is acyclic, but inserting any one new edge into creates a cycle.

3. Prove the following claims:
1. Every tree with at least two nodes contains at least two leaves.
2. Let be an arbitrary graph, and a leaf (= node of degree 1) in . Then is a tree, if and only if the graph (= the subgraph of spanned by nodes ) is a tree.

4. 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)?

5. A hypercube graph has as nodes all the -bit binary sequences , and nodes and are connected by an edge if and only if the corresponding binary sequences differ in exactly one position.
1. Draw pictures of the graphs and . How many nodes are there in graph ?
2. For which values of does contain a closed Eulerian tour?
3. Determine the diameter of graph , i.e. the biggest possible internode distance in , , where the distance between nodes is defined as the length of the shortest path connecting them.

6. Prove, by induction on , that every hypercube graph , , contains a Hamiltonian cycle. (Hint: Assume inductively that graph contains a Hamiltonian path from node to node . Observe that two such paths can be connected into a similar Hamiltonian path in .) Draw pictures of the Hamiltonian paths based on this construction for the graphs and .

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