Example 5. (Hefei Mathematical Competition Question in 1983) A new station is opened, and several bus routes are planned to serve the community. Their wishes are: (1) to open as many routes as possible; (2) each route must have at least one bus stop; (3) ensure that each bus stop is served by at least two different routes. Under these conditions, what is the maximum number of routes they can open? How many stops should each route have at minimum?
Solution
Let be the number of lines that can be opened, and consider the lines as vertices to form a graph . Label the 1983 stations as . If two lines have a common station, color the edge between the corresponding two vertices with color .
From (2), every edge of can be colored;
and (3), the number of different colors used on any two different edges of is
From (1), can only be 63. From the above solution process, it is easy to see that at most 63 lines can be opened; and because each vertex of is connected to 62 edges of different colors, each line must pass through at least 62 stations.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.