Graph Theory Eulerian Path Define the cube graph Cn as foll

Graph Theory - Eulerian Path

Define the cube graph C_n as follows: There are 2^n vertices, labeled 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?

Solution

A graph is eulerian if and only if it is connected and every vertex has even degree. In this hypercube graph as described above , vertices will have even degree if and only if n is even.

So for n even and only for n even this will have Eulerian path

Observe that for n binary representation of any number has at most n digits

and so any vertex can be linked (have edge with )to n other vertices