Browse · MathNet
Print59th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
In a country, the government has decided to build a transport link between cities by railway or airline in such a way that no more than four other cities can be reached directly from each city. Prove that the government can always choose the type of connection of the corresponding pairs of cities in such a way that there are no three cities, each pair of which is connected by one type of transport. (Arseniy Nicolaev)
Fig. 42
Fig. 43
Solution
Let's rewrite the problem statement in terms of graphs: in the graph the degree of each vertex is not more than four. Prove that all edges can be painted in two colors so that there are no single-color triangles. Let our graph have vertices. We prove the statement of the problem by induction on the number of vertices.
Base case: if everything is obvious Assume the statement is true for any graph with vertices. Consider a graph with vertices. Select the vertex arbitrarily. Remove this vertex from the graph as well as all edges from . Thus we have a graph with vertices, that, by the induction hypothesis, can be painted as needed. Now paint vertex with its edges. Consider three cases.
I. The degree of each vertex is not more than 2. Then paint all edges from in different colors, which proves the problem statement.
II. The degree vertex is equal to 3, that is there is exactly 3 edges and (Fig. 42); the dotted line means it is not significant whether there is a corresponding edge. We know that the edges of have different colors. Let, for instance, be painted in the first color – the second color. Let's paint the edges as shown on Fig. 42: and – in the second color, and – first. By the induction hypothesis the statement is proved.
Fig. 42
III. The degree vertex is equal to 4, that is there are the following edges from : and .
a) If the graph on the vertices is complete, we have a separate connected component on the vertices . Wherein by the induction hypothesis it is a complete graph. Then let's paint its edges as shown on Fig. 43 and the statement is proved. Since all other vertices form a graph with less then vertices, by the induction hypothesis, it is painted as needed.
Fig. 43
b) If the graph on the vertices is not complete, suppose there that there is no edge . Let's paint the edges in a color, opposite to the edge , and the edges – in a color, opposite to the edge . It is straightforward to check that there are no single-color triangles. Hence, by the induction, the problem statement is proved.
Base case: if everything is obvious Assume the statement is true for any graph with vertices. Consider a graph with vertices. Select the vertex arbitrarily. Remove this vertex from the graph as well as all edges from . Thus we have a graph with vertices, that, by the induction hypothesis, can be painted as needed. Now paint vertex with its edges. Consider three cases.
I. The degree of each vertex is not more than 2. Then paint all edges from in different colors, which proves the problem statement.
II. The degree vertex is equal to 3, that is there is exactly 3 edges and (Fig. 42); the dotted line means it is not significant whether there is a corresponding edge. We know that the edges of have different colors. Let, for instance, be painted in the first color – the second color. Let's paint the edges as shown on Fig. 42: and – in the second color, and – first. By the induction hypothesis the statement is proved.
Fig. 42
III. The degree vertex is equal to 4, that is there are the following edges from : and .
a) If the graph on the vertices is complete, we have a separate connected component on the vertices . Wherein by the induction hypothesis it is a complete graph. Then let's paint its edges as shown on Fig. 43 and the statement is proved. Since all other vertices form a graph with less then vertices, by the induction hypothesis, it is painted as needed.
Fig. 43
b) If the graph on the vertices is not complete, suppose there that there is no edge . Let's paint the edges in a color, opposite to the edge , and the edges – in a color, opposite to the edge . It is straightforward to check that there are no single-color triangles. Hence, by the induction, the problem statement is proved.
Techniques
Coloring schemes, extremal argumentsInduction / smoothing