Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bit strings & Graph theory

  1. Mar 31, 2005 #1
    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.


    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.
  2. jcsd
  3. Mar 31, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Apr 16, 2005 #3
    sounds like hte hypercube if i remmeber correctly.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook