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, 07: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, 07:44 PMNonCommAlg
isn't it obvious? suppose the vertex is $\displaystyle \bold{x}=x_1x_2 \cdots x_n,$ where each $\displaystyle x_j$ is either 0 or 1. let $\displaystyle \bold{0}=00 \cdots 0.$ if $\displaystyle \bold{x}=\bold{0},$ there's nothing to prove. otherwise let $\displaystyle k=\min \{j: \ x_j=1 \}.$

then there exists an edge between $\displaystyle \bold{0}$ and $\displaystyle \bold{y}_1=0 \cdots 0 x_k 0 \cdots 0.$ now if $\displaystyle x_j=0, \ \forall \ j > k,$ then $\displaystyle \bold{y}_1=\bold{x}$ and we're done. otherwise let $\displaystyle \ell = \min \{j > k: \ x_j=1 \}.$ then there exists

an edge between $\displaystyle \bold{y}_1$ and $\displaystyle \bold{y}_2=0 \cdots 0 x_k 0 \cdots 0 x_{\ell} 0 \cdots 0.$ again if $\displaystyle x_j=0, \ \forall j > \ell,$ then $\displaystyle \bold{y}_2=\bold{x}$ and we're done. otherwise repeating this process, say $\displaystyle m$ times, eventually will give

us a path from $\displaystyle \bold{0}$ to $\displaystyle \bold{y}_m=\bold{x}.$