- #1
miraclepie
- 1
- 0
I am not really sure how to start this problem, and I have tried searching everywhere. If you could help me that would be great...just to know how to get started. I'm in 2nd Year, Intro to discrete mathematics, if it matters. Thanks
Let G be a graph whose vertices correspond to the bit-strings of length n.
a=a1a2...an
Where ai= 0 or 1, and whose edges are formed by joining those bit-strings which differ in exactly two places.
a) show that G is regular, that is, every vertex has the same degree, and find the degree of each vertex.
b) Find a necessary and sufficient condition that there exist a path joining two vertices a=a1a2…an and b=b1b2…bn in G.
c) Find the number of connected components of G.
Let G be a graph whose vertices correspond to the bit-strings of length n.
a=a1a2...an
Where ai= 0 or 1, and whose edges are formed by joining those bit-strings which differ in exactly two places.
a) show that G is regular, that is, every vertex has the same degree, and find the degree of each vertex.
b) Find a necessary and sufficient condition that there exist a path joining two vertices a=a1a2…an and b=b1b2…bn in G.
c) Find the number of connected components of G.