Discrete structure- gray code

2. In the recursive definition for the Gray code, G+1, given in the text, and assuming G, satisfies the properties of a Gray code, explain concisely: (a) Why the string in position n and the string in position n+1 differ only in one bit (b) Why, for i 1...n-1, the string in position i and the string in position i+ 1 differ only in one bit. (c) Why, for i n 1...2n-1, the string in position i and the string in position it differ only in one bit. Fortunately, our solution will apply to the n-cube for any positive value of n. A Hamiltonian circuit of the n-cube can be described recursively. The circuit itself, called the Gray Code, is not the only Hamiltonian circuit of the n-cube, but it is the easiest to describe. The standard way to write the Gray Code is as a column of strings, where the last string is followed by the first string to complete the circuit. Basis for the Gray Code (n = 1): The Gray Code for the 1-cube is G = CHAPTER 9. GRAPH THEORY 221 1. Note that the edge between 0 and 1 is used twice in this circuit. That doesn't violate any rules for Hamiltonian circuits, but can only happen if a graph has two vertices. Recursive definition of the Gray Code: Given the Gray Code for the n-cube, n12 1. then G +1 is obtained by (1) listing G, with each string prefixed with 0. and then (2) reversing the list of strings in G with each string prefixed with 1. Symbolically, the recursion can be expressed as follows, where G is the reverse of list G . GG 06 The Gray Codes for the 2-cube and 3-cube are 000 001 011 010 110 101