# Graph Theory question: hamiltonian path ...

• Jan 17th 2013, 10:53 PM
MageKnight
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?
• Jan 18th 2013, 01:33 AM
jakncoke
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.
• Jan 18th 2013, 01:44 AM
emakarov
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.