4.71 In a certain state, there are several cities, and between every two cities, there is exactly one of three means of direct transportation: car, train, and airplane. It is known that all three means of transportation are used throughout the state; however, no city has all three means of transportation; and there are no three cities where the means of transportation between each pair of cities are all the same. How many cities can there be at most in the state?
[Solution] Represent each city with a point, and connect the corresponding two points with a red, yellow, or blue line according to whether the transportation between the two cities is by car, train, or plane. According to the problem, the graph has the following properties:
(1) There is one line between every two points, colored red, yellow, or blue;
(2) The graph contains edges of all three colors;
(3) Among all the edges originating from each vertex, there are at most two different colors;
(4) The graph does not contain any monochromatic triangles, i.e., triangles with all three sides of the same color.
All vertices can be divided into three categories: non-red, non-yellow, and non-blue. A vertex in the non-red category means that none of the edges originating from this vertex are red, and the meanings of non-yellow and non-blue are similar. Of course, a vertex may belong to two of these three categories.

If a vertex $A$ has three edges of the same color, say red edges $A B, A C, A D$, then by (4), the edges $B C, B D, C D$ cannot be red. Suppose $B C$ is a blue edge, then vertices $B$ and $C$ are both non-yellow vertices, so $B D$ and $C D$ can only be blue edges. This way, $\triangle B C D$ would be a blue triangle, which contradicts (4). Therefore, the number of edges of the same color originating from a vertex is at most two, so the graph can have at most 5 vertices.

Suppose there are 5 points $A, B, C, D, E$, where $A$ and $B$ both belong to the non-red category, and assume $A B$ is a blue edge. By (4), among the three pairs of edges $\{A C, B C\}, \{A D, B D\}, \{A E, B E\}$, each pair must have at least one yellow edge. Also, by (2), there must be at least one red edge among the points $C, D, E$, so there must be a vertex that is non-blue, say $C$. Thus, $A C$ and $B C$ are both yellow. Therefore, $C D$ and $C E$ are both red, and $A D$ and $A E$ are one blue and one yellow. If $D E$ is a red edge, then $\triangle C D E$ would be a red triangle, which is a contradiction; if $D E$ is a yellow or blue edge, it would lead to vertex $D$ or $E$ having edges of all three colors, which is also a contradiction. Therefore, there can be at most 4 cities.

When there are 4 vertices, assume they are the 4 vertices of a convex quadrilateral. When the 4 sides are all red and the two diagonals are one yellow and one blue, it clearly meets the requirements of the problem. Therefore, the state can have at most 4 cities.