Linking 5 communities by plane, train, and bus

Question

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?)

score 1 · Accepted Answer · answered Feb 12 '14 at 03:47

1

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.

answered Feb 12 '14 at 03:47

Rebecca J. Stones

26,845

Is my solution wrong? – Asinomás Feb 12 '14 at 03:57
It doesn't seem to cover the possibility of this not being true: "Then there are three edges of the same color coming out of it." – Rebecca J. Stones Feb 12 '14 at 04:01
Case 1 is clear, but I'm still confused about case 2. What do you mean by three edge disjoint cycles? – user115697 Feb 12 '14 at 04:12
In Case II, if we consider edges in only one color class (i.e., the edges of one color), then every vertex has degree 0 or 2. With $5$ vertices, these edges form single cycles and isolated vertices. – Rebecca J. Stones Feb 12 '14 at 04:14

Linking 5 communities by plane, train, and bus

1 Answers1