Cube Graph
Discrete Mathematics
Level
2
Define the cube graph \( C_n \) as follows:
There are \( 2^n \) vertices, labelled \( v_0, v_1, \ldots, v_{2^n-1} \). Draw an edge between \( v_a \) and \( v_b\) if and only if the binary representations of \( a \) and \( b\) differ in exactly one digit.
We would like to find a path along the cube graph \( C_n \) that crosses each edge exactly once, and begins and ends at the same vertex. For \( 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 \) or \( n = 4 ? \)
by
Patrick Corn