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.
"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?
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?