Thread: 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?

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

If is a hamiltonian circuit, then each vertex except for gets repeated once which would mean, that each pair of points except for would different by atleast one coordinate (otherwise they would be the same point no?), which is to say if then there exists a j such that , which is an edge that exists within our graph W.

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.