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.