# Homework Help: Hamiltonian Path - Induction Proof

1. May 2, 2013

### brojesus111

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. May 2, 2013

### christoff

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.

3. May 2, 2013

### brojesus111

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
4. May 2, 2013

### christoff

No, you aren't missing anything; it's just a very easy problem.

5. May 2, 2013

### brojesus111

Oh, ok. Thanks for the help!