# path from the vertex ??

• May 8th 2009, 07:04 PM
sanorita_belle
path 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.

• May 8th 2009, 07:44 PM
NonCommAlg
Quote:

Originally Posted by sanorita_belle

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.

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}.$