Graph Theory question: hamiltonian path ...

Hello together :)

Ok, let's start:

http://fed.matheplanet.com/mprender....999&mixmod=mix

Now show that W contains every circuit, that contains every vertex exactly once. This circuit is called hamiltonian circuit.

Well, I really do not even know where to start.. Maybe someone can give me a hint?

Re: Graph Theory question: hamiltonian path ...

Isn't this kinda obvious? Unless i am misunderstanding the question.

If $\displaystyle H = u^1 \to u^2 \to ... \to u^1 $ is a hamiltonian circuit, then each vertex except for $\displaystyle u_1 $ gets repeated once which would mean, that each pair of points except for $\displaystyle (u^i, u^i) $ would different by atleast one coordinate (otherwise they would be the same point no?), which is to say if $\displaystyle i \not = p $ $\displaystyle u^i \to u^p $ then there exists a j $\displaystyle 1 \leq j \leq 5 $ such that $\displaystyle u^i_{j} \not = u^p_{j} $, which is an edge that exists within our graph W.

Re: Graph Theory question: hamiltonian path ...

Quote:

Originally Posted by

**MageKnight** Now show that W contains every circuit, that contains every vertex exactly once. This circuit is called hamiltonian circuit.

Why are you saying that W contains "every" Hamiltonian circuit? Every graph contains every Hamiltonian circuit that it contains, possibly none. :) The interesting claim is that the hypercube contains *some* Hamiltonian circuit.

The graph that is defined in the linked image is K₃₂, the complete graph on 32 vertices, and not a hypercube. It is trivial to see that a complete graph is Hamiltonian. The graph would be a hypercube if

u, v ∈ E ⇔ ∃ *unique* i; 1 ≤ i ≤ 5 with uᵢ ≠ vᵢ

See Wikipedia about the existence of a Hamiltonian circuit in a hypercube. It seems that it is easier to prove it for hypercubes of any dimension n by induction on n. (This brings to mind the joke about an engineer who was asking a mathematician how to visualize a 9-dimensional vector space, and the mathematician advised to first visualize an n-dimensional space and then put n = 9.) It may be convenient to prove simultaneously two facts by induction: the existence of a Hamiltonian circuit and the existence of a Hamiltonian path between any two adjacent vertices.