Cube Graph
Define the cube graph C n as follows:
There are 2 n vertices, labelled v 0 , v 1 , … , 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 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
When n=3: the path 0-1-3-2-6-7-5-4-0 will cover all vertices and the edge wiil be visited exactly once?
Log in to reply
Now you're missing 1-5, 3-7, 0-2, and 4-6. There are 12 edges.
You are hitting all the vertices, but the question asked you to traverse all the edges. You're missing lots of those. (E.g. for n=3 you are missing 0-4, 6-7, 2-3, 1-5.)
Log in to reply
For n=odd there is no solution because: For some number at the begin and the end of the sequence we have - if occurs - two additionally adjacent numbers in the middle which results in an even number of adjacent neighbours. But for n=odd only an odd number of neighbours can be taken into account.
However for n=even this required combination works! A sequence for n=4 for example is:
0-1-3-2-10-8-12-13-9-11-15-7-5-1-9-8-0-4-5-13-15-14-6-7-3-11-10-14-12-4-6-2-0
Log in to reply
G̶r̶e̶a̶t̶!̶ ̶C̶o̶u̶l̶d̶ ̶y̶o̶u̶ ̶a̶d̶d̶ ̶t̶h̶a̶t̶ ̶t̶o̶ ̶t̶h̶e̶ ̶s̶o̶l̶u̶t̶i̶o̶n̶ ̶d̶i̶r̶e̶c̶t̶l̶y̶?̶ ̶J̶u̶s̶t̶ ̶h̶i̶t̶ ̶t̶h̶e̶ ̶e̶d̶i̶t̶ ̶b̶u̶t̶t̶o̶n̶.̶
I've added your comment into the solution.
I was wondering what would be the answer for n=5 and n=6 ?
Path does Not exist for n=3 & n=4
n=3 =>
000 (0) -> 001 (1) -> 011 (3) -> 010 (2) -> 110 (6) -> 111 (7) -> 101 (5) -> 100 (4) -> 000 (0) [ok.. got it.. i missed other edges..]
for n=4 =>
0000 (0) -> 1000 (8) -> 1001 (9) -> 1011 (11) -> 1010 (10) -> 1110 (14) -> 1100 (12) -> 1101 (13) -> 1111 (15) -> 0111(7) -> 0101 (5) -> 0100 (4) -> 0110 (6) -> 0010 (2) -> 0011 (3) -> 0001 (1) -> 000 (0) [ missed other edges.. too ]
not possible .. since each vertex has more >= 2 degree unless n=2. you can choose nc1 ways to flip the digit.. all lying <= 2^n-1 , or any one of them. each vertex will hv n edges .. to travarse all of them u need to visit more than one of them n-1 times.
like handshaking..
for n bits..
0000 (0001, 0010, 0100, 1000) 0001 (0000, 0011, 0101, 1001) 0010 (0000, 0011, 0110, 1010) 0011 (0010, 0001, 1011, 0111) ...
Where am i wrong??
the given scenario is possible for even power of 2 (Similarity with Grey code?? )
Log in to reply
You made the assumption that "each vertex can only be traversed once", which is not true. All that we want is a path that "crosses each edge exactly once".
There are 2 n vertices. So, each vertex can be identified using n bits. For example, each of 2 3 = 8 vertices can be represented using 3 bits: { 0 0 0 , 0 0 1 , 0 1 0 , 0 1 1 , 1 0 0 , 1 0 1 , 1 1 0 , 1 1 1 } .
Each vertex is connected to another if and only if their bit representation differs by one bit. Since each vertex is represented by n bits, there are n other vertices that differ in exactly one bit. So, every vertex is of the same degree n .
Hence, the graph is connected, and its vertices are either all odd or all even. To have a Eulerian path on a connected graph, there must be exactly 0 or 2 odd vertices. n = 3 has 2 3 > 2 odd vertices of degree 3. n = 4 has 2 4 even vertices of degree 4 and no odd vertices.
Hence, a path exists for n = 3 but does not exist for n = 4 .
Two comments : (1) you got the conclusion in the wrong order, i guess it's only a typo. the path does not exist for n=3, and exists for n=4. (2) here we need the path to begin and end at the same vertex, so we are looking for an Eulerian circuit, not a path. Therefore the graph must have 0 odd vertex.
For odd n there is no solution, because:
For some number at the begin and the end of the sequence we have - if occurs - two additionally adjacent numbers in the middle which results in an even number of adjacent neighbors. But for odd n only, an odd number of neighbors can be taken into account.
However for even n , this required combination works! A sequence for n = 4 for example is:
0 − 1 − 3 − 2 − 1 0 − 8 − 1 2 − 1 3 − 9 − 1 1 − 1 5 − 7 − 5 − 1 − 9 − 8 − 0 − 4 − 5 − 1 3 − 1 5 − 1 4 − 6 − 7 − 3 − 1 1 − 1 0 − 1 4 − 1 2 − 4 − 6 − 2 − 0