Results 1 to 2 of 2

Math Help - path from the vertex ??

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    14

    Unhappy 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.

    Someone please help!

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by sanorita_belle View Post

    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!
    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}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with vertex's in a 3d space
    Posted in the Geometry Forum
    Replies: 4
    Last Post: July 4th 2011, 01:57 PM
  2. Replies: 2
    Last Post: June 9th 2010, 07:39 AM
  3. degree of a path, path homotopy.
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 19th 2009, 05:37 PM
  4. Vertex?
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 1st 2008, 02:41 PM
  5. Locus of The Vertex
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 14th 2008, 11:58 AM

Search Tags


/mathhelpforum @mathhelpforum