Problem Set 7, 7 - 9 November

- 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.
- Draw pictures of all nonisomorphic 6-node trees.
- Prove that there are at least
distinct isomorphism types of -node trees.
(
*Hint:*Apply the Sylvester-Cayley tree counting theorem and the inequality .)

- Prove that a graph is a tree, if and only if it
is acyclic, but inserting any one new edge into creates
a cycle.
- Prove the following claims:
- Every tree with at least two nodes contains at least two leaves.
- 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.

- Determine the Prüfer codes of the following trees
(cf. Balakrishnan, pp. 168-169):
- 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.- Draw pictures of the graphs and . How many nodes are there in graph ?
- For which values of does contain a closed Eulerian tour?
- 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.

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