Graphs, The Traveling Salesman Problem, and P vs NP

This activity is for a computer science class or a discrete math class when students first learn about graphs and efficiency of algorithms. This could also be used as an enrichment activity for high school students since it is self-contained with all definitions given and there isn’t any specific background knowledge needed.