Write a proof for the given using mathematical induction.

Needs:

1. Base case

2. Induction Hypothesis

3. Induction Goal.

Question:We are told that a particular country has nstates, with n> 1, and that from each state x to each other state y there is a highway that may be travelled in only one direction - we are not told which. We want to prove that for any such country, there is a path starting at one state, visiting each state exactly once, and ending (if n > 1) at a different state. This path uses n 1 of the roads and travels each road in the correct direction.