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(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Bit strings & Graph theory

**Physics Forums | Science Articles, Homework Help, Discussion**