What are the properties and connections between bit strings and graph theory?

[miraclepie]

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.

 

[shmoe]

If you really have no clue on how to do a question like this, the first thing I'd do is look at some concrete examples. Try to work out the question for n=1, 2, 3, and maybe 4 if you need to (1 and 2 should be exceedingly dull). By working out these examples, you should be able to see why a) is true, and probably guess on what the degree will be for a given n as well as a conjecture for b) and c) in the general case.

Hopefully these specific examples will give some insight into the general case, and you will get some idea on how to start the general proofs. One more thing, for n=3 (and 1 and 2 I guess) it might help to arrange your vertices as though the bits represented coordinates in R^3, so they are the vertices of a cube.

If you try this and still need more help, feel free to ask.

 

[neurocomp2003]

sounds like hte hypercube if i remmeber correctly.