What is the girth and circumference of 4-dimensional cube?

Question

What is the girth and circumference of Q4 (4-dimensional cube, a graph on 16 vertices)，how can I prove it?

Girth means the length of a shortest cycle，and circumference means the length of a longest cycle.

Answer 1

The girth is the length of the shortest cycle. This is probably the easier part of the question. What possible lengths can cycles have? If you just work your way up from the smallest possible length, you should be able to see which actually occur.

I'm going to write $abcd$ for $(a,b,c,d)$, the coordinates of a vertex, where each letter can be either $0$ or $1$. Note that adjacent vertices differ in exactly one coordinate.

You can't have a cycle of length less than $3$. Since adjacent vertices differ in exactly one coordinate there can't be any cycles of odd length. But you can have a cycle of length $4$ (e.g. $0000,0001,0011,0010,0000$).

The circumference is the length of the longest cycle.

If I were working with a normal cube (it saves a lot of writing) I could visit every vertex to get a cycle of length 8:

$000$ $001$ $011$ $010$ $110$ $111$ $101$ $100$ $000$

I can't do any better than this because I can't repeat vertices, so the circumference would be $8$. You might want to try extending this approach to your cube.

Answer 2

For $n\ge 2$, the $n$-cube has a Hamiltonian cycle. See for instance http://en.wikipedia.org/wiki/Hypercube_graph