A certain country wishes to interconnect $2021$ cities with flight routes, which are always two-way, in the following manner: • There is a way to travel between any two cities either via a direct flight or via a sequence of connecting flights. • For every pair $(A, B)$ of cities that are connected by a direct flight, there is another city $C$ such that $(A, C)$ and $(B, C)$ are connected by direct flights. Show that at least $3030$ flight routes are needed to satisfy the two requirements.
Problem
Source: PMO 2021
Tags: combinatorics, PMO
gnoka
24.03.2021 11:30
Fist of all, for a single vertex A, there are points B,C such that AB,AC,BC are all connected. We can call it a system. Since the graph is a connected graph, there is a vertex outside the system (we can call it D), connected with a vertex inside the system. (WLOG, suppose it's A). So there is a vertex X connected with both D and A. If the vertex X is inside the system, the system get 2 more edges and 1 more vertexes. We call it "M development". If the vertex X is outside the system, the system get 3 more edges and 2more vertexes. We call it "N development". it's obvious that we can find a route, after m times M development and n times N development, the system develop into the whole graph. Suppose it has X edges now. We have $m+2n+3=2018; X \geq 2m+3n+3= \frac 1 2 m +3030$ since $m \geq 0, X \geq 3030,$ it's trival that 1010 triangles with 1 common vertex hold. so we are done.
P2nisic
06.03.2024 22:28
See also here: https://artofproblemsolving.com/community/c6h208558p1148103 Roumania 2008 TST