1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Hamiltonian Path - Induction Proof

  1. May 2, 2013 #1
    1. The problem statement, all variables and given/known data
    Let G be a graph.
    1. Let n be a natural number. Use induction to show for all n >= 2 Kn has a Hamiltonian path.
    2. Explain how you could use the proof from #1 to show that for all n (natural number) n > 2 Kn has a Hamiltonian cycle.

    2. Relevant equations

    3. The attempt at a solution

    So Kn refers to a complete graph - I know that much. And the n refers to the number of vertices. I'm not sure how to begin the proof for #1.

    For #2, the subgraph excluding one vertex is Kn-1 has a path. We can connect the ends together through the excluded vertex to make a cycle.
  2. jcsd
  3. May 2, 2013 #2
    For part 1, can you show that K2 has a a Hamilton path?
    Then, by induction, suppose Kn has a Hamilton path. You know that Kn is a subgraph of K(n+1); so what then can you say about the existence of a Hamilton path in this subgraph? Show that this can be extended to a Hamilton path in K(n+1). In fact, this path can be extended in precisely two ways.
  4. May 2, 2013 #3
    So K2 has a Hamilton path is our base case, and that is obvious since it is just two vertices and we can easily visit each point once.
    Our induction hypothesis is that we assume Kn has a Hamilton path.
    For our inductive step, we want to show that this holds true for n+1. As you said, Kn is a subgraph of K(n+1). Since K(n+1) is a complete graph, then every vertex has a unique edge, so we can just travel along that edge to make that a Hamilton path since we assumed Kn has a Hamilton path.

    I'm assuming I'm missing something here.
    Last edited: May 2, 2013
  5. May 2, 2013 #4
    No, you aren't missing anything; it's just a very easy problem.
  6. May 2, 2013 #5
    Oh, ok. Thanks for the help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted