May 2021 Problem of the Month

Mr. P has friends in the following ten cities:
Bangalore (Karnataka, India)
Beechworth (Victoria, Australia)
Delta (Colorado, USA)
Flint (Michigan, USA)
Fort Collins (Colorado, USA)
Grand Junction (Colorado, USA)
Mobile (Alabama, USA)
Mountain View (Wyoming, USA)
Mumbai City (Maharashtra, India)
Pune (Maharashtra, India)


He wishes to set up airline service between the cities with the following restrictions:
For any two cities, A and B, you should be able to take a trip starting at A and visit all the other cities exactly once ending at B.
What is the smallest number of connections (between 2 cities) that is needed to accomplish this?

Extra Credit: If there were 1,001 cities instead of just ten, what is the smallest number of connections needed?

---

For example, if there were four cities A, B, C, and D.
You would need the following six connections: AB, BC, CD, DA, AC, and BD.
For cities A and B: A - C - D - B.
For cities A and C: A - B - D - C
For cities A and D: A - B - C - D
For cities B and C: B - A - D - C
For cities B and D: B - C - A - D
For cities C and D: C - A - B - D

Here is a picture of the six connections: