Show that there is a path from the vertex 00..... 0, the bit string with n zeroes, to any vertex in n-cube, for n >=1.

Someone please help!

Printable View

- May 8th 2009, 08:04 PMsanorita_bellepath from the vertex ??Show that there is a path from the vertex 00..... 0, the bit string with n zeroes, to any vertex in n-cube, for n >=1.

**Someone please help!**

- May 8th 2009, 08:44 PMNonCommAlg
isn't it obvious? suppose the vertex is where each is either 0 or 1. let if there's nothing to prove. otherwise let

then there exists an edge between and now if then and we're done. otherwise let then there exists

an edge between and again if then and we're done. otherwise repeating this process, say times, eventually will give

us a path from to