In the state of Roadland (sorry for the terribly unimaginative name), there are 42 major cities. Some of these cities are connected by roads, where each road connects exactly two cities, and there is at the most one road between any two cities. Inhabitants of Roadland also try to remove obvious superfluity from there road network: so if any three cities A, B and C are such that there is a road from A to B, and one from B to C, then there would not be any road from A to C. How many roads can there be in Roadland? (Based on a well known but simple graph theoretical result)
No comments:
Post a Comment