We have seen that for n 1, the n-cube Qn is the graph whose vertex...

Transcribed Image Text:

We have seen that for n ≥ 1, the n-cube Qn is the graph whose vertex set is the set of n-bit strings, where two vertices of Qn are adjacent if they differ in exactly one coordinate. (a) For n ≥ 2, define the graph Rn to be that graph whose vertex set is the set of n-bit strings, where two vertices of Rn are adjacent if they differ in exactly two coordinates. Draw R₂ and R3. (b) For n ≥ 3, define the graph Sn to be that graph whose vertex set is the set of n-bit strings, where two vertices of Sn are adjacent if they differ in exactly three coordinates. Draw S3 and S4. We have seen that for n ≥ 1, the n-cube Qn is the graph whose vertex set is the set of n-bit strings, where two vertices of Qn are adjacent if they differ in exactly one coordinate. (a) For n ≥ 2, define the graph Rn to be that graph whose vertex set is the set of n-bit strings, where two vertices of Rn are adjacent if they differ in exactly two coordinates. Draw R₂ and R3. (b) For n ≥ 3, define the graph Sn to be that graph whose vertex set is the set of n-bit strings, where two vertices of Sn are adjacent if they differ in exactly three coordinates. Draw S3 and S4.

Answer rating: 100% (QA)

SOLUTION First we prove that C 1 is non bipartite Let us assume the ... View the full answer