Hamiltonian Path - Induction Proof

[brojesus111]

Homework Statement

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.

Homework Equations

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.

 

[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.

 

[brojesus111]

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.

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.

 

[christoff]

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

 

[brojesus111]

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

Oh, ok. Thanks for the help!