Euler cycle & Hamiltonian cycle

Euler cycle

An Euler cycle in a graph G is a cycle that passes through every edge of G only once.

Theorems

A graph G has an Euler cycle if and only if G is a connected graph and every vertex has even degree.

---

Hamiltonian cycle 

Hamiltonian cycle in a graph G is a cycle that visit every vertex of G only once by a simple cycle.

n-Cube

The n-cube, denoted I^n (n>=1), has 2^n vertices labeled 0, 1, 2, ..., 2^(n-1) , and edges connecting two vertices if the binary representation of their labels differ in exactly one bit.

n-Cube can be made from (n-1)-Cube by the following rules:

1) Let H1 and H2 be two (n-1)-Cubes whose vertices are labeled in binary 0, ..., 2^(n-1)-1.

2) Place an edge between each pair of vertices, one from H1 and one from H2, provided that the vertices have identical labels.

3) Change the label L on each vertex in H1 to 0L and change the label L on each vertex in H2 to 1L.

Gray code and Hamiltonian cycle 

 The n-Cube has a Hamiltonian cycle(n>=2).

Let Gn a n-bit Gray code, then that is a Hamiltonian cycle in n-Cube.

Gn is made from G(n-1) by the following rules:

(a) Let G^R(n-1) denote the sequence G(n-1) written in reverse.

(b) Let G'(n-1) denote the sequence obtained by prefixing each member of G(n-1) with 0.

(c) Let G''(n-1) denote the sequence obtained by prefixing each member of G^R(n-1) with 1.

(d) Let Gn be the sequence consisting of G'(n-1) followed G^n(n-1).