7・81 Suppose 20 telephones are connected by wires, each wire connecting two telephones, and at most 1 wire connects any pair of telephones; from each telephone, at most 3 wires can extend out. Now, we want to paint each of these wires with 1 color, such that the colors of the wires extending from each telephone are all different. What is the minimum number of different colors needed?
[Solution] When the connections are as shown in the right figure, at least 4 different colors are required.
The following proves that using 4 different colors is sufficient. Represent each telephone with a point, and when two telephones are connected by a wire, draw a line segment between the corresponding points. Thus, we obtain a graph with 20 vertices, where each vertex is connected by at most 3 edges. The graph will contain some cycles and some chains, and the number of edges in a cycle or chain is called its length. First, find the longest cycle in the graph. If it contains an even number of edges, then color these edges alternately with color 1 and color 2; if it contains an odd number of edges, then color one of the edges with color 3, and the rest with color 1 and color 2 alternately. After coloring, remove this cycle and all the edges extending from the vertices on this cycle (these edges have not been colored yet). Then, find the longest cycle in the remaining graph and color it in the same way, removing this cycle and all the edges extending from the vertices on this cycle. Continue this process until there are no more cycles in the graph. At this point, find the longest chain in the remaining graph and color the edges of this chain alternately with color 1 and color 2. Then remove this chain and all the edges extending from the vertices on this chain. Continue this process until there are no more chains in the graph. At this point, the remaining graph consists of isolated points. Now, consider the coloring of the edges that were removed but not yet colored during the above process. For those edges whose endpoints are both vertices on colored cycles or internal vertices of chains (non-endpoints), they can all be colored with color 4. For those edges with one endpoint being an isolated point, the other endpoint must be a vertex on a cycle or an internal vertex of a chain (otherwise, the isolated point should be connected to a chain), so at each such endpoint, there are two edges already colored. If an isolated point is connected to 3 edges, and the other endpoints of these edges are connected to two edges colored 1 and 2, then one of these edges can be recolored to 3 (this is possible because each cycle has at most one edge colored 3), and the edge between the isolated point and this vertex can be colored with the original color of this edge (1 or 2). The other two edges extending from the isolated point can then be colored with 3 and 4, respectively. If an isolated point is connected to 3 edges, and the other endpoints of these edges are connected to two edges colored 1 (or 2) and 3, then the 3-colored edge at one endpoint can be swapped with its other neighbor, and the edge between the isolated point and this vertex can be colored with 3. The other two edges extending from the isolated point can then be colored with 2 (or 1) and 4, respectively. For other cases, it is even easier to handle. For cases where one endpoint is the endpoint of a chain, similar handling can be done, at most recoloring the last edge of the chain to 3.
In summary, the minimum number of different colors required is 4.