1. ## Optimization problem

Being a physicist, I'm not very familiar with the optimization problems in discrete mathematis. I don't know how to formally prove the following:

A town has n horizontal and m vertical streets aligned in a square grid so that there are n x m crossings. Neighboring crossings are distanced by a unit length. What's the smallest length of the road that one must construct so that every crossing is connected to every other by the road?

My solution is L = n x m - 1. I've constructed numerous examples and still can't find a counterexample. But I have no idea how to prove this. Any help will be greatly appreciated.

2. Two thoughts come to mind: you're dealing with the taxicab geometry here. Also, I doubt very much whether you can get every crossing without your L as a minimum, because of the fencepost problem.

Those are my thoughts.

3. Thank you for the links. I'm affraid I don't understand what you meant by "get every crossing without your L as a minimum".

4. "Get every crossing" just a rephrase of "traverse very crossing", or "connect every crossing by a road." If you think about this problem in terms of graph theory, then your crossings are vertices, and the roads are edges. If you have n vertices, you'll require a minimum of n-1 edges to connect all the vertices. In your case, with m x n crossings (vertices), you'll need m x n - 1 roads to connect all the crossings, as a minimum. Does that clarify things?

5. Yes, thank you, that was the argument I needed. I'm not used to think in terms of graph theory.

6. Just a thought here: it makes a big difference that all the crossings must be connected to all the other crossings. The basic problem in graph theory is the minimum edge cover problem. But what you're really trying to solve is a minimum connected edge cover problem, which is definitely different. Another name for this problem is the minimum spanning tree problem, where all the weights are equal. I would use the pigeon-hole principle to prove the desired result. If you use fewer edges than your L, a vertex is going to have to be omitted from the tree, right?

7. I think that proof by induction is the simplest one and will suffice.

8. Induction sounds like it would work just fine. You're planning on inducting on the number of vertices, I'm assuming?

9. Yes, I will prove by induction that the general vertices can be connected this way and then that one can always find a system of roads of that length.

10. I think that'll work for you. Just show that the number of roads can't be less than L, and then show that you can construct a path of length L that satisfies the conditions, and you'll be done. Good luck!