Results 1 to 3 of 3

Math Help - Graph Theory question: hamiltonian path ...

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Germany
    Posts
    2

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    388
    Thanks
    80

    Re: Graph Theory question: hamiltonian path ...

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

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

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Graph Theory question: hamiltonian path ...

    Quote Originally Posted by MageKnight View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory path decomposition
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 22nd 2012, 02:19 PM
  2. Replies: 0
    Last Post: April 9th 2011, 08:57 AM
  3. Replies: 9
    Last Post: July 20th 2010, 08:00 AM
  4. complexity theory {Hamiltonian, DHC, IND}
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2010, 10:13 AM
  5. Graph Theory Hamiltonian Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 08:41 PM

Search Tags


/mathhelpforum @mathhelpforum