Cube Graph

Probability Level 2

Define the cube graph Cn C_n as follows:

There are 2n 2^n vertices, labelled v0,v1,,v2n1 v_0, v_1, \ldots, v_{2^n-1} . Draw an edge between va v_a and vb v_b if and only if the binary representations of a a and b b differ in exactly one digit.

We would like to find a path along the cube graph Cn C_n that crosses each edge exactly once, and begins and ends at the same vertex. For C2 C_2 this is possible: start at 0, move to 2, move to 3, move to 1, move back to 0.

What about for n=3 n = 3 or n=4? n = 4 ?

×

Problem Loading...

Note Loading...

Set Loading...