Any two islands of the Chaos Archipelago are connected by a bridge - a red bridge or a blue bridge. Show that at least one of the following two assertions holds:
A1: For any two islands a and b, we can reach b from a through at most 3 red bridges (and no blue bridges).
A2: For any two islands a and b, we can reach b from a through at most 2 blue bridges (and no red bridges).
Alternative formulation: Let G be a graph. Prove that the diameter of G is ≤3 or the diameter of the complement of G is ≤2.
Note. This problem is the main Theorem in
Frank Harary, Robert W. Robinson, The Diameter of a Graph and its Complement, The American Mathematical Monthly, Vol. 92, No. 3. (Mar., 1985), pp. 211-212.
darij combinatorics proposedcombinatorics