# 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 $\bold{x}=x_1x_2 \cdots x_n,$ where each $x_j$ is either 0 or 1. let $\bold{0}=00 \cdots 0.$ if $\bold{x}=\bold{0},$ there's nothing to prove. otherwise let $k=\min \{j: \ x_j=1 \}.$
then there exists an edge between $\bold{0}$ and $\bold{y}_1=0 \cdots 0 x_k 0 \cdots 0.$ now if $x_j=0, \ \forall \ j > k,$ then $\bold{y}_1=\bold{x}$ and we're done. otherwise let $\ell = \min \{j > k: \ x_j=1 \}.$ then there exists
an edge between $\bold{y}_1$ and $\bold{y}_2=0 \cdots 0 x_k 0 \cdots 0 x_{\ell} 0 \cdots 0.$ again if $x_j=0, \ \forall j > \ell,$ then $\bold{y}_2=\bold{x}$ and we're done. otherwise repeating this process, say $m$ times, eventually will give
us a path from $\bold{0}$ to $\bold{y}_m=\bold{x}.$