(this post may be of interest to readers with knowledge of mathematics and sympathizers)

The other day I read about an interesting problem from graph theory - the road coloring conjecture. This hypothesis has been open for 37 years, but three years ago it was proved by the Israeli mathematician Abraham Trachtman. The proof turned out to be quite elementary, and with some difficulties (since the brains atrophied) I was able to read and understand it, and I will even try to explain it in this entry.

The problem can be explained with the following example. Imagine a city map where you can drive in one of four directions at each intersection - north, south, east and west. If the car starts from some intersection and follows some list of directions - "north, north, east", etc. - then she will eventually arrive at some other intersection. Can you find a list of directions, perhaps a long one, that will take the car to the same place, no matter where it starts? If the map looks like Manhattan - a regular grid - then no, but maybe there are many dead ends and unexpected turns in it?

Or another example. Your friend got stuck in a maze to find a center and called you for help. You know how the maze works, but you don't know where your friend is. Could there be a sequence of commands that will definitely bring your friend to the center, wherever he is?

In these two examples, the "directions" at each point are fixed, and the solution either exists or it does not. But in a more general case, this problem asks: if we can choose where it shows, for example, "west, north, east, south", at each intersection in its own way, can we then ensure the existence of a "sync word" - a sequence of commands that any place will lead to one fixed?

In the general case, let there be a directed graph G - with "arrow" edges between the vertices. Let this graph have a uniform outgoing degree d - this means that exactly d edges go out of each vertex. In this case, each individual vertex can be entered different amount, optional d. Suppose we have a set of d letters of some alphabet, which we will call "flowers". Then the "coloring" of the graph is given by assigning for each vertex all d letters for d of its outgoing edges. So if we "are" at some vertex, and want to “go” somewhere according to the color α, then the coloring will always tell us which edge we need to go to which new vertex. Any sequence of letter-colors is called a "word". Then, if a coloring is given in the graph, and x is some vertex, and w is some word, then xw denotes the vertex to which we will come, starting with x and following the word w.

The coloring is called synchronizing if there is a word w that leads any vertex x to one fixed vertex x 0. In this case, w is called sync word... The question that the road coloring problem asks is: is there always a sync coloring? Is it always possible to color the edges of a graph so that all the vertices can be reduced to one?

This problem has applications in several different areas, which you can read about, for example, on Wikipedia. Let's say, in computer science, in the theory of automata. A graph with a coloring can be viewed as a deterministic finite automaton, in which the vertices are states, and the edges indicate how to pass between them. Suppose we control this machine from a distance, sending commands through some information channel, and due to some breakdowns this channel was dirty, the machine received some erroneous instructions, and now we do not know at all what state it is in. ... Then, if there is a sync word, we can bring it to a known state, no matter where it is now.

So when does sync coloring exist? The road coloring conjecture imposes two more restrictions on the graph (except that exactly d edges go out from each vertex). First, the graph must be strongly connected, which means that there is a route from any vertex to any other. Secondly, the graph should not be periodic. Imagine that all the vertices of the graph can be divided into sets V 1, V 2, ... V n, so that any edge of the graph connects vertices from some V i and V i + 1 or V n and V 0. There are no edges between the vertices in each V, and they also cannot "jump" between any V, only in order. Such a graph is called periodic. It is clear that such a graph cannot have a synchronizing coloring, because no matter how you color it and what words you use, two vertices in different V i will never converge - they will continue to walk in a cycle.

The road coloring theorem says that these conditions are sufficient: any non-periodic, strongly connected directed graph with d edges from each vertex has a synchronizing coloring... It was first formulated as a hypothesis in 1970, and since then there have been many partial results proving particular cases, but a complete proof appeared only in 2007. What follows is my retelling of almost the entire proof (except for one technical lemma).

Periodicity

First of all, we replace the non-periodicity condition with another equivalent to it. The graph is periodic if and only if there is a number N> 1, which divides the length of any cycle in the graph. Those. our requirement of non-periodicity is equivalent to the fact that there is no such N, or in other words, the greatest common divisor of the lengths of all cycles in the graph is 1. We will prove that any graph satisfying this condition has a synchronizing coloring.

To prove that periodicity is equivalent to the condition "there is N> 1, by which the length of any cycle is divisible" is trivial in one direction and easy in the other. If you are willing to take this on faith, you can easily skip the rest of this paragraph, for the rest of the proof it does not matter. If the graph is periodic, i.e. it is possible to divide the vertices into sets V 1, V 2, ... V n, so that the edges go between them in a cycle, then it is obvious that the length of any cycle must be divisible by n, i.e. the new condition is met. This is a trivial direction, but for our replacement we need just the second direction. Suppose there is an N> 1 that divides the length of any cycle. Let's build some directed spanning tree in our graph with the root at the vertex r. There is a route to any vertex x in this tree starting from the root of length l (x). We now assert that for any edge p -> q in the graph, it is true that l (q) = l (p) + 1 (mod N). If this statement is true, then it immediately follows that we can split all vertices into sets V i according to l (x) mod N, and the graph will be periodic. Why is this statement true? If p -> q is part of a spanning tree, then this is obvious, because then just l (q) = l (p) + 1. If this is not the case, then we write the routes from the root r to the vertices p, q as R p and R q. Let also R r denote a route from q back to r in the graph (the graph is connected, so it exists). Then we can write two cycles: R p p -> q R r, and R q R r. According to the hypothesis, the lengths of these cycles are divisible by N, subtracting and canceling the common values, we obtain that l (p) +1 = l (q) mod N, as required.

Stable friendship and induction

Let some coloring of the graph G be given. Let us call two vertices p, q friends if some word w brings them to one vertex: pw = qw. Let's call p, q enemies if they "never get together". Let us call p, q stable friends if after executing any word w they remain friends: pw may not come to the same vertex as qw, but after some more w "it will be able to come. Stable friends never become enemies.

The stability relation between the vertices is, firstly, equivalence (it is reflexive, symmetric and transitive), and secondly, it is preserved by the structure of the graph: if p, q are stable friends, p is connected by an edge with p ", q with q", and these edges of the same color, then p "and q" are also stable friends. This means that a stable friendship is congruence and it can be divided into it: create a new graph G ", the vertices of which will be equivalence classes for stable friendship in G. If G has at least one stable pair, then G" will be less than G. Moreover, if in the original graph G from each vertex has d edges, then it will be so in G ". For example, if P is a vertex of a new graph, which is the equivalence class of the original vertices p1, p2 ..., and α is any color, then the edges p1 - α -> q1, p2 --- α -> q2, etc. all lead to the vertices q1, q2 ..., which are in stable friendship with each other, and therefore lie in one new vertex Q, so that all these edges become a new edge P --α -> Q. And so for each of d colors.

Moreover, if G was non-periodic, then G "is. After all - using our alternative definition of periodicity - any cycle in G turns into a cycle in G", so if all the lengths of cycles in G "are divisible by n> 1, then the same is true for all cycles in G. So that the periodicity of G "implies the periodicity of G.

Suppose we managed to find a synchronizing coloring in G ". It can now be used in G instead of the coloring we started with: any edge p -> q will get a new color according to the new color of the edge P -> Q. A little more precisely should be said so: at each vertex P of the graph G "a new coloring is given by some permutation of all colors π P: an edge that was painted in color α receives a new color π P (α). Then, in the original graph G, at each vertex p from the stability class P, we apply the same permutation π P to recolor its edges. Generally speaking, the new coloring of the graph G defines some new concepts of "friendship", "enmity" and "stability" that are not identical to the original ones. But nevertheless, if two vertices p, q were stable friends in the old coloring - they belonged to the same class P - then they will remain stable friends in the new one. This is because any sequence w that brings p, q to one vertex can be "transferred" from the old coloring to the new one, or vice versa, using the permutation π P at each vertex p along the road. Since p, q are stable in the old coloring and remain so "all the way", each intermediate pair of vertices p n, q n along the road from p, q to the common vertex will be stable, that is, lie inside one vertex P n and therefore obtain the same permutation π P n.

The new color is synchronizing for G ", that is, some sequence w brings all the vertices to one vertex P. If we now apply w to the new color in G, then all the vertices will converge somewhere" inside P ". As indicated above, all vertices inside the class P remain stable in the new coloring, which means that now we can continue w, again and again bringing together the remaining separate pairs of vertices until everything converges into one vertex G. Thus, the new coloring is synchronizing for G.

All this implies that in order to prove the theorem, it is enough to prove that in any graph satisfying the conditions there is a coloring in which there are a couple of stable friends. Because then from the graph G one can go to the graph G "smaller in size, and it also meets all the conditions. Using the inductive argument, we can assume that for graphs of smaller size the problem has already been solved, and then the synchronizing coloring for G" will also synchronize for G ...

Clicks and Maximum Sets

For any subset A of vertices of the graph and word w, Aw denotes the set of vertices we arrive at, starting from all vertices of A and following the word w. If we start from all vertices of the graph in general, then we denote it by Gw. In this notation, sync coloring means that there is a w such that Gw is a set of one element.

If the set of vertices A has the form Gw for some w, and besides, any two vertices in A are enemies, that is, never converge, let's call A clique... Cliques exist because we can always start with an integer G, take a pair of friend vertices, traverse the w that connects them, and decrease the number of vertices by one; continue this way until there are no enemies left or only one vertex remains - in this case, too, a clique, simply trivial.

If A is a clique, then for any word w Aw is also a clique; this is clear because enemies remain enemies. If x is any vertex of the graph, then there is a clique that includes x. This follows from the fact that there is some kind of clique A (see the previous paragraph); if p is a vertex in it, that is, the word w leading from p to x, since the graph is connected; then Aw is a clique including x.

The cliques will help us prove that there is a coloring with stable friends - according to the previous section, this is enough to prove the theorem. Throughout this section, we will prove that if there are two cliques A and B, so that all vertices in them are common, except one in A and one in B, then these two vertices are stable friends. Thus, the problem is reduced to finding a coloring in which there are such cliques A and B.

In order to better understand how cliques work, it turns out to be useful to assign weights to the vertices in the graph. Let us show that we have a way to assign a positive weight w (x) to each vertex x, so that if for any vertex x sum the weights of all vertices from which the edges go to x, then you get d * w (x), where d is the number of edges from each vertex. This follows from linear algebra, and if you don't know what an eigenvalue is, skip the rest of this paragraph and take the existence of such w (x) for granted. If M is the matrix of the graph G (cell (i, j) contains 1 if there is an edge i -> j, and 0 if there is no such edge), then w (x), as I described them, are elements of the eigenvector left for this matrix for the eigenvalue d. We know that such a vector exists because d is an eigenvalue: it has a trivial eigenvector on right(1,1, .... 1) - this immediately follows from the fact that exactly d edges go out of each vertex.

If A is any set of vertices, then w (A) denotes the sum of the weights of all vertices from A; and w (G) is the sum of the weights of all vertices in the graph. In addition, if s is any word, then Let As -1 denote the set of vertices to which you come from A, if you go "in the opposite direction" along s, at each step replacing each vertex with those vertices (if any) that go to it in the appropriate color.

Consider now all the sets of vertices that can be brought together to one point, i.e. such A such that for some w Aw contains only one vertex. Those sets A which among all such have the maximum weight w (A) are called maximal sets. If the coloring is synchronizing, then the entire graph G is the maximal set (the only one), but otherwise it is not so.

If A is any set of vertices, then the sum of all w (Aα -1), where α runs through all d colors, is equal to d * w (A) - this is just a generalization of the main property of a weight from one vertex to a set of vertices A. If, in addition, moreover, A is a maximal set, then each of w (Aα -1) cannot be greater than w (A), because these sets also reduce to one vertex. And since the sum d of these weights is equal to d * w (A), it turns out that each of them is equal to w (A), and all these sets are also maximal. This immediately implies that if A is maximal, then Aw -1 is also maximal for any word w.

Maximal sets are useful because their disjoint instances can cover the entire graph. Let's prove it.

Suppose we have a collection of maximal sets A 1 ... A n that do not intersect in pairs and are reducible to single vertices a 1 ... an by the same word w (in the initial case, there will be n = 1 and only one set, so it's easy to get started). It is clear that all a 1 ... a n differ from each other, because otherwise it would be possible to expand the maximum set even more at the expense of elements of another with the same final vertex. Suppose that all A i together have not yet exhausted all vertices of G, and let x be a vertex outside all A i. Since the graph is connected, there is some route h from a 1 to x. Then n maximal sets A ih -1 w -1 go over the word whw to the final vertices a 1 ... an, and the maximal set A 1 goes to some vertex Awhw = (Aw) hw = (a 1 h) w = xw. This vertex xw must also differ from all a 1 ... a n, because otherwise the maximum set A i could be replenished with an element x. And since all these n + 1 sets - all A i h -1 w -1 plus A 1 - go along whw to different vertices, they all do not intersect in pairs. We will continue this expansion until there are no vertices outside the set.

So, we can cover the whole graph G with disjoint maximal sets. Since they are maximum, they all have the same entire w max, and therefore their number in the coverage is equal to N max = w (G) / w max.

Now consider any set A consisting of pairwise enemies. For example, a clique is an example of such a set (and also has the form Gw). There cannot be a pair of enemies inside the maximum set, because then it could not converge. Hence, in a cover of N max maximal sets, each contains at most one member A, so the size of A is at most N max. In particular, this is the upper limit on the size of any click.

Let A be a clique of the form Gw, where w is some word. Then G = Aw -1, and accordingly w (G) is equal to the sum w (aw -1), where a runs through all the vertices of A. The number of terms, according to the previous paragraph, is not more than N max, and each set aw -1 can be reduced to one point (to point a by the word w), so its weight is not more than the maximum w max. Since the whole sum is equal to w (G) = N max * w max, we conclude that the number of terms is exactly equal to N max, and each term is exactly equal to w max. We proved that all cliques have the same size: exactly N max elements.

Let there be two cliques A and B, so that inside A all elements are common with B, except one: | A | - | A∩B | = 1.

Since A and B have the same size, we also have | B | - | A∩B | = 1, i.e. all elements of A and B are common, except for one vertex p in A and one vertex q in B. We would like to prove that these vertices p, q are stable friends. If they are not, then some word w makes them enemies, i.e. pw and qw are enemies. As shown above, Aw and Bw are also cliques, and it is obvious that they again have all elements in common, except for the enemies pw and qw. Then the set Aw ∪ Bw is the set of pairwise enemies. Indeed, in it all the elements Aw are pairwise enemies, because this is a clique; the same is true for the elements Bw; and only a pair of pw remained, qw - also enemies. But this set has N max +1 elements, and above we showed that in any set of pairwise enemies there cannot be more than N max elements. This is a contradiction, and therefore pw and qw cannot be enemies for any w. In other words, p and q are stable friends.

Spanning graphs and clicks

Let from the given graph G we took all the vertices, and from each vertex we chose only one outgoing edge. This choice determines a subgraph, which we will call spanning graph(spanning graph). There can be a lot of different spanning graphs, but let's think a little about how they look. Let there be some spanning graph R. If we take any vertex x in it and start following its edges, then each time we will have only one choice, because in R there is only one edge coming out of each vertex, and sooner or later we will close cycle. Maybe this cycle will not close at x, but close somewhere "further" - for example, x -> y -> z -> s -> y. Then the "tail" will lead from x to this cycle. If we start from some other vertex, we will also come to a cycle - this or some other. It turns out that any vertex R either lies on the cycle (of which there can be several), or is part of the "tail" that leads to the cycle. This means that R looks like this: a certain number of cycles, and a certain number of "inverted" trees are built on them: each tree does not begin, but ends at a "root" that lies on one of the cycles.

To each vertex of the graph, we can assign level corresponding to its distance to the cycle in the given spanning graph R. cycle. Some vertices of our graph have a maximum level L. Perhaps it is generally equal to 0 - that is, there are no trees, just cycles. Perhaps it is greater than zero, and the vertices of this maximum level lie on all sorts of different trees connected to different cycles or to the same one.

We want to choose a spanning graph R in such a way that all vertices of the maximum level lay on the same tree... Intuitively, you can believe that this can be done, because if this is not so - for example, they are scattered over different trees - then you can choose one of such maximum vertices x and increase its level by joining some edge to R going to x. Then some other edge will have to be thrown out, and it is not a fact that this will not harm something else ... but this is a technical question, which will be discussed later. I'm just trying to say that this doesn't seem very complicated intuitively.

For now, suppose you can choose R so that all vertices of the maximum level lie on the same tree. This tree is assumed to be non-trivial, i.e. the maximum level is L> 0. Based on this assumption, we construct a coloring with cliques A and B in it that meet the conditions of the previous section, and this will prove that this coloring contains a stable pair of friends.

The coloring will be as follows: choose some color α, and color all edges in the graph R in this color, and all other edges in the graph G - in some other colors in any way (if there is only one color, then R coincides with G so no problem). Thus, words consisting of the color α "move" the vertices of R along their trees towards the cycles, and then drive them along the cycles. We only need such words.

Let x be any vertex of the maximum level L in R, and let K be any clique that includes x; we know that such a clique exists. Can K include some other top of the maximum level L? According to our assumption, all such vertices are in the same tree as x, which means that the word α L brings them to the same place as x - namely, to the root of this tree lying on the cycle. Hence, all such vertices are friends of x, and therefore cannot lie in the same clique with it. Therefore, in addition to x, K can include only vertices of a lower level.

Let's look at the set A = Kα L-1. This is also a clique, and in it all vertices, except x, have reached some of their cycles in R, because all vertices of A, except x, have level less than L. Only x is still outside the cycle, at a distance of exactly 1 to its root on the loop. Now let's take some number m that is a multiple of all cycle lengths in R - for example, the product of all cycle lengths. M has such a feature that if the vertex y is on a cycle in R, then the word α m returns it to its place: yα m = y. Let's look at the clique B = Aα m. All vertices of A, except x, were on the cycles, and therefore remained in the same place in B; and only x finally entered its cycle and settled there somewhere. This means that the intersection of A and B contains all the vertices of A except one: | A | - | A∩B | = 1. But this just means, according to the previous section, that our coloring has a stable pair, which is what we had to prove.

Building the maximum level.

It remains to prove that one can always choose a spanning graph R so that it has a nontrivial maximum level L> 0, and all the vertices of this level lie on the same tree.

Part of this proof is a rather boring and technical lemma that I read and checked, but I will not retell it, I will just tell you where it is in the article, for those who are interested. But I will tell you how to get to this lemma.

We need two restrictions that we can impose on the graph G. First, we say that G has no loops, that is, edges from a vertex to the same vertex. The point is that if there is a loop in the graph, then it is very easy to find the synchronizing coloring in another way. Let's color this loop in some color α, and then, going from this vertex in the opposite direction "against the arrows", color the edges so that the color α always leads to this vertex. Due to the connectedness of the graph, this is easy to arrange, and then the loop ensures that some degree of α will reduce the entire graph to this vertex.

Further, suppose for a second that from some vertex p all d edges lead to the same vertex q. This is allowed by the conditions, but in this case we will call this set of edges bundle... Our second constraint is this: there is no vertex r to which two connectives from different vertices p and q lead. Why can we impose it? Because if connectives go from p and q to r, then for any coloring p, q will converge at the vertex r after the first color, and therefore they are stable friends. So in this case we don't need all the spanning graphs and cliques constructions, we get stable friends right away. Therefore, we can assume that this is not the case.

Finally, let us prove that there always exists a spanning graph R in which not all vertices lie on cycles, but there are some nontrivial trees. Let's choose some R, and suppose that all vertices in it lie on cycles. If in the graph G all edges were in connectives, i.e. always all d edges outgoing from one vertex lead to the same vertex - then the choice of R would include only the choice of one edge from each bundle. In this case, R could have only one cycle (after all, several cycles in R could in no way be connected to each other in a connected graph G - all the edges of G connect only the same vertices as the edges of R, because these are connectives - and once G is connected, this is impossible), and any cycle in G simply selects other edges from the connectives of this cycle, but in fact it is the same cycle, of the same length. But this means that the lengths of all cycles in G are divisible by this length, which just contradicts the non-periodicity of G. Therefore, it cannot be that all the edges in G lie on connectives, which means that there are some two edges p-- > q in R, and p -> s outside R (we needed a long argument about connectives to prove that some edge from p not only does not lie in the spanning graph, but also leads to another vertex s). Then we replace p -> q by p -> s, and this will "split" the cycle, creating some kind of non-trivial tail in it. This tail will give us a non-trivial tree in the new graph.

Now we can choose from all spanning graphs R in which there are nontrivial trees, some R that is maximal in terms of the number of vertices on the cycles. T.e. it has vertices not on cycles, but besides this limitation, the number of vertices on cycles is maximized. This graph contains some vertices of the maximum level L, and we can assume that they are on trees leading to different roots, otherwise we have already achieved what we need. Let us choose one such vertex x. We want to change the graph so that this vertex becomes part of a longer route in the tree, longer than L, and the other trees do not change, and then the maximum level will be in only one tree, which is what we need. There are three ways to change the graph:

a) take some edge y -> x, and add it to R, and discard the existing edge y -> z;
b) take the edge b -> r, which is just the last one on the path from x to its cycle (r on the cycle), and discard it, and add some other b -> z.
c) take an edge c -> r, which is part of the cycle, and discard it, and add some other edge c -> z.

In Lemma 7 of Trachtman's article, it is proved in detail that one (or in some case two) of these changes lead to the desired result. The process uses both the maximality of R (if some change leads to a graph with more than in R, the number of vertices on cycles, this contradicts its maximality), and the condition defined above that there is no vertex to which two connectives lead. As a result, in any case, we obtain a graph R in which all vertices of the maximum level lie on one nontrivial tree.

Update, a week later: I decided, nevertheless, to make this entry completely self-sufficient and to retell the proof of the lemma to which I referred in the previous paragraph. It would be better to do this with a diagram, but I don't feel like drawing it or tearing it out of the article, so I'll try with words. So, imagine that we have a spanning graph R, in which there are nontrivial trees, and of all such graphs in it maximum amount the vertices lie on the cycles. We strive to transform R into a spanning graph in which all vertices of the maximum level lie on the same tree; as soon as in the process of trying we get such a graph, then we finish right away (and we don't care that the maximality of the graph in terms of the number of vertices on the cycles can be lost, it is not important to us in and of itself, we only use it in the process). Let x be the vertex of the maximum level L, T the tree on which it lies, r the vertex on the cycle C where T ends, b -> r the last edge before r on the path from x to the cycle C. We can assume that there are some other trees joining this cycle or others, which have vertices of level L - otherwise everything is already done. It follows from this that if we can get from T a tree with an element of greater degree than L, and not lengthen these other trees, then we are done.

First, let's try to do operation a) above: take some edge y -> x in G - it exists, since the graph is connected and without loops, and does not lie in R, since x maximum level. Let's add it to R, and discard some y -> z that was there before. If y lies on a tree T, then y -> x closes a new cycle, and in the new graph more vertices lie on cycles, and there are still nontrivial trees (at least those others that were in R), which contradicts the maximality of R. If y does not lie on T, and y -> z is not part of the cycle C, then removing y -> z does not break this cycle, and adding y -> x lengthens the maximum level of the tree T by at least one, while others trees don't lengthen, so we're done. The only option left is when y -> z lay on cycle C, which has now crashed, and a new cycle is formed: from r to y, then y -> x, then from x to r along the former tree. The length of this cycle is l (ry) + 1 + L, and the length of the old cycle C was l (ry) + 1 + l (zr). The new cycle cannot be longer than the old one, this contradicts the maximality of R, therefore we see that L ≤ l (zr), i.e. the length of the route from z to r in the old loop. On the other hand, in the new graph, now the vertex z has a level of at least l (zr), and if this is greater than L, then we are done. So we can assume that l (zr) = L. To summarize: we assume that a) does not work, and then we know that y -> z lies on the cycle C, l (zr) = L.

Now let's try operation b): replace the edge b -> r with some other edge b -> d. Let's see where the new vertex d is. If on a tree T, then we created a new cycle without breaking the previous one, and refuted the maximality of R. If on another tree, then the maximum vertices of T, including x, will now have a level greater than L, and other trees will not, and we are done ... If on another cycle, not C, then we will now do along with b) also a): since we know that y -> z lies on C, then this operation will split C, but not the new cycle to which we are now connected tree Τ, and this tree will now have vertices of a level greater than L, and we are done again.

The option remains when b -> d is also connected to the cycle C, in some other place than r, or in the same place, and then d = r. After we replaced b -> r with b -> d, we got the same situation as initially - tree T, vertex x of level L, etc. - the tree is now connected to the cycle only through the vertex d. Considering now operation a), we conclude (assuming that it does not work) that l (zd) = L, just as we concluded earlier that l (zr) = L. But if l (zd) = l ( zr), i.e. the distance along the cycle from z is the same to d and r, then this is the same vertex: d = r. So, if b) doesn't work, then any edge from b must lead to r, i.e. the edges from b form a bundle.

Finally, consider an edge c -> r lying on a cycle C. Since we can assume that all edges from b lie on a connective leading to r, and we can also impose the constraint, which was mentioned above, that there cannot be two connectives leading to one vertex, not all edges from c lead to r, but there is some edge c -> e. Replace c -> r with c -> e. Where can vertex e lie? Not on the tree T, because this would "extend" the cycle C, contradicting the maximality of R. Hence, e lies on another tree or on another cycle, or even on the same cycle C, but not at the vertex r. Then the tree T, before it connects to the cycle, is now lengthened by at least one edge outgoing from r, and maybe by more (only one if e lies immediately after r, and c -> e closes the cycle C again, deriving only r from it). This means that the level of the vertex x and other maximum vertices of T is now at least L + 1, and the other trees have not lengthened, and again we got what we need.

Site update
10.12.2006 15:46
For lovers of cars and cartoons - coloring pages from the cartoon Cars.

Thanks to Disney and Pixar, in June 2006, the whole world saw a cartoon in which only cars became heroes.

Cars in Cars live a normal life - one runs a rubber store, the other a tuning studio, and some just live for fun, like the hippie Fillmore (Volkswagen T1) or his friend, a WWII veteran Serge (Willys). The main character of the film McQueen, nicknamed "Lightning", dreams only of races, victories and glory. Once in Radiatorny District on the famous American Highway 66, the "green" McQueen immediately tells everyone how fast and cool he is. However, the very first start in the NASCAR race dispels his illusions. Friends help the hero survive the loss - the old tow truck Mater (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) and little Luigi (Fiat 600), who dreams of seeing a real Ferrari.

Well, where can we go without the romantic beauty Sally (Porsche with a charming 911 tattoo)! Largely thanks to them, McQueen will still win the race, defeating the main rival Chico (Plymouth Hemi Cuda). Luigi's dream will also come true - one day a "stallion from Maranello", voiced, by the way, by "The Red Baron" Michael Schumacher, will come to his store to change the tires.

It is noteworthy that both the creators of the picture and those who voiced it are people involved in cars. For example, director Joe Lasseter spent most of his childhood at the Chevrolet plant, where his father was one of the chief designers. Jay Mays, the lead designer of the Ford concern, acted as a consultant. In addition to the already mentioned seven-time Formula 1 world champion Michael Schumacher, NASCAR stars Richard Petty and Paul Newman, as well as legendary racer Michael Andretti, took part in the dubbing of the heroes.

The noise of the cars was used only original - for example, especially for racing episodes, the sound was recorded for several weeks on American ovals during NASCAR competitions. It took more than two years to create the picture, the budget of which was USD 70 million. During this time, 43 thousand different sketches of machines were created, and each drawing took more than 17 hours. A total of 120 car characters in the film - from new Porsches and Ferraris to an antique Ford T.

You are in the road coloring page. The coloring that you are looking at is described by our visitors as follows "" Here you will find many online coloring pages. You can download road coloring pages and print them for free. As you know, creative activities play a huge role in the development of a child. They activate mental activity, form aesthetic taste and instill a love for art. The process of coloring pictures on the theme of the road develops fine motor skills, perseverance and accuracy, helps to learn more about the world around, introduces the whole variety of colors and shades. Every day we add new free coloring pages for boys and girls to our website, which you can color online or download and print. A convenient catalog, compiled by categories, will facilitate the search for the desired picture, and a large selection of coloring pages will allow you to find a new interesting topic for coloring every day.

You can keep the boys busy for a long time if you invite them to play with cars in the sandbox. But what to do if it is cold outside, the child is bored. In this case, you can download and print the following road car templates. The fun starts with cutting out all the rings, turns and straight roads. With these templates, the child can build a road of any shape, just make sure that the proper number of the necessary A4 sheets is printed.

Download a straight road for cars

You will need these sheets the most. On an A4 sheet, we have placed 3 roads that need to be printed and cut out. Show your child how to cut the road at right angles to make the section as long as he or she wants.

Car road: ring

To connect roads, you need a ring, the template of which is presented above, and start building your infrastructure with it.

Car Road: Straight Bend

The presented turns will allow the boy to turn the road at 90 degrees, in the direction he needs.

Not a sharp turn in the road for cars

The following A4 template will help you to wrap the road under any radius.

Child's knowledge of the Rules road traffic- one of the main conditions for his safety on the street. Many pedestrians, including adults, are rather frivolous about the observance of these rules, which often becomes the cause of traffic accidents of various severity. Children should clearly understand that being on the street in the village, they are full participants road traffic, therefore, compliance with traffic rules is their responsibility.

Coloring pages Rules of the road for children.

Teaching a child the rules of behavior on the street (roads, sidewalks, city transport) should be started at a very early age, before he learns to walk and run on his own. And here the example of parents and other adults with whom the child is on the street is very important. You must not only tell and explain the traffic rules to your child, but also strictly follow them yourself. The traffic rules coloring pages presented on this page are primarily intended for preschoolers and will help children learn the main points of behavior on the road, as well as near it.

1. Coloring Traffic Light.

The best place to safely cross a road is a pedestrian crossing with a traffic light. Coloring pages with a picture of a traffic light also contain small rhymes to help kids more easily remember the rules for using it.

• Always start driving only when the green traffic light is on.
• Never cross the road when traffic signals are red or yellow, even if there are no vehicles nearby.
• Turning to the green light, additionally make sure that you are safe - look to the left, then to the right.

2. Coloring pedestrian crossing.

Teach your child to cross the carriageway only at a pedestrian crossing. Coloring pages of pedestrian crossings will teach children how to cross the road correctly. A crossing that is not equipped with a traffic light is called unregulated.

• The pedestrian crossing is marked on the road surface with a "zebra".
• Before crossing the road, carefully inspect it, make sure there is no transport nearby.
• Cross the road, don't cross.
• Do not cross the street obliquely.
• Pay special attention to standing vehicles that obscure your view.
• Stop talking on the phone while driving on a pedestrian crossing.
• If there are underground or overground passages nearby, be sure to use them, in such places the traffic is especially intense.

3. Sidewalks.

The sidewalk is intended for pedestrian traffic. Teach children to behave correctly on sidewalks, especially in areas with heavy traffic.

• When driving on the sidewalk along the road, do not get too close to it.
• Watch carefully for possible exit of cars from courtyards and lanes.
• Do not play ball on the sidewalk, do not run.

4. Coloring pages with the rules of behavior for children in city public transport and at bus stops.

These coloring pages will teach children how to use public transport safely.

• Public transport stop - dangerous place due to a possible poor view of the road and a large crowd of people who can accidentally push a child off the sidewalk into the carriageway. You need to be especially careful here.
• Approach the door of the vehicle only after it has come to a complete stop.
• Leaving the transport, proceed to the road crossing only after it leaves the stop.

In addition to these basic rules of the road, children will be interested in coloring road signs. The presented traffic rules coloring pages are suitable for toddlers, preschoolers and junior students school age, as well as for use in kindergartens and lessons in primary grades schools. All pictures with Traffic Rules are completely free - you can download and print them.