We now construct a graph G on 8 vertices as follows. Let B = {0000, 0001, …, 1111} be the set of bit-strings of length 4. There are exactly 16 such bit-strings. Vertices: We say a bit-string is sorted if the four bits in the bit-string occur in increasing order or in decreasing order. E.g. the three bit-strings 0011, 0000, and 1110 are sorted, and the two bit-strings 1001 and 1101 are not sorted. Exactly 8 of the 16 bit-strings in B are sorted. Let the vertex set V be comprised of the 8 bit-strings in B that are sorted. Edges: We include the edge (u,v) in E between the two bit-strings u and v if u and v differ in exactly one position. That is, if three of the four bits in u and v are the same, and one bit differ. How many edges does G contain? (The answer is an integer)
Question 10 options:
We now construct a graph G on 8 vertices as follows.
Let B = {0000, 0001, …, 1111} be the set of bit-strings of length 4. There are exactly 16 such bit-strings.
Vertices: We say a bit-string is sorted if the four bits in the bit-string occur in increasing order or in decreasing order. E.g. the three bit-strings 0011, 0000, and 1110 are sorted, and the two bit-strings 1001 and 1101 are not sorted. Exactly 8 of the 16 bit-strings in B are sorted. Let the vertex set V be comprised of the 8 bit-strings in B that are sorted.
Edges: We include the edge (u,v) in E between the two bit-strings u and v if u and v differ in exactly one position. That is, if three of the four bits in u and v are the same, and one bit differ.
How many edges does G contain? (The answer is an integer)
Step by step
Solved in 2 steps
