Every pair of communities in a country is linked directly by exactly one mode of transportation: bus, train or airplane.
All three modes of transportation are used in the country; no community is served by all three modes, and no three communities are linked pairwise by the same mode. For example, four communities can be linked according to these stipulations in the following way: bus, AB, BC, CD, DA; train, AC ; airplane, BD.
Give a proof to show that five communities cannot be linked in the required manner.
Is there any way to do this other than brute force (going through all the possibilities and showing contradictions arise?)
Case I: Some vertex is the endpoint of $3$ edges of the same color. The triangle $T$ formed by the other endpoints of these three edges is either monochromatic (violating one condition) or some vertex of $T$ is the endpoint of three distinctly colored edges (violating another condition).
Case II: Every vertex is the endpoint of $2$ edges of one color and $2$ edges of another color. The color classes therefore partition the edges of $K_5$ into three edge-disjoint cycles. Since there are no monochromatic triangles, each cycle contains $4$ or more edges, but this implies there's $\geq 4+4+4=12$ edges in $K_5$, giving a contradiction.