My road to school coloring book. Rules of the road coloring pages

Site update
10.12.2006 15:46
For fans 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 the cartoon Cars ("Cars") live ordinary lives - one keeps a rubber shop, the other a tuning studio, and some just live for their own pleasure, such as the hippie Fillmore (Volkswagen T1) or his friend - a veteran of World War II Serge (Willys). The main character of the picture McQueen, nicknamed "Lightning", dreams only of racing, victories and glory. Once in the Radiator District on the famous US Highway 66, the "green" McQueen immediately tells everyone how fast and cool he is. However, the first start in the NASCAR race dispels his illusions. Friends help the hero survive the loss - the old Meiter tow truck (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) and little Luigi (Fiat 600), who dreams of seeing a real Ferrari.

Well, where 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" will call in his shop to change tires, which, by the way, was voiced by the "Red Baron" Michael Schumacher himself.

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 factory, where his father was one of the chief designers. Jay Mays, the leading 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 the legendary racer Michael Andretti, took part in voicing the heroes.

Only the original car noise was used - for example, specially 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 70 million USD. During this time, 43 thousand different sketches of cars were created, and each drawing took more than 17 hours. There are a total of 120 car characters in the film, from new Porsches and Ferraris to antique Ford Ts.

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

Download straight road for cars

These sheets will be needed most of all. On a sheet of A4 format, we 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 the length he needs.

Road for cars: ring

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

Car Road: Straight Turn

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

Not a sharp turn of the road for cars

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

You are in the road coloring page. Coloring page you are looking at is described by our visitors as follows "" Here you will find a lot of coloring pages online. You can download road coloring pages and also print them for free. As you know, creative activities play a huge role in the development of the child. They activate mental activity, form an aesthetic taste and instill a love of 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 us, introduces you to all the 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 make it easier to find the right picture, and a large selection of coloring pages will allow you to find a new interesting topic for coloring every day.

A child's knowledge of the Rules of the Road is one of the main conditions for his safety on the street. Many pedestrians, including adults, are rather frivolous about observing these rules, which often becomes the cause of traffic accidents of various severity. Children must clearly understand that being on the street in the village, they are full participants in the road, so 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, urban 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 rules of the road to your child, but also strictly observe them yourself. The traffic rules coloring pages on this page are primarily intended for preschoolers and will help children learn the basics of behavior on the road, as well as near it.

1. Traffic light coloring page.

The best place to cross the road safely is at a pedestrian crossing equipped with traffic lights. Traffic light coloring pages also contain small rhymes to help kids remember the rules for using it more easily.

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

2. Coloring the pedestrian crossing.

Teach your child to cross the carriageway only at a pedestrian crossing. Coloring pages of pedestrian crossings will teach children 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 surface of the road with a zebra.
• Before crossing the road, carefully inspect it, make sure that there is no traffic nearby.
• Cross the road, don't run across.
• Don't cross the street.
• Pay special attention to standing vehicles that block your view.
• Stop talking on the phone while walking across a pedestrian crossing.
• If there are underground or elevated passages nearby, be sure to use them, in such places the traffic is especially intense.

3. Sidewalks.

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

• When driving on the sidewalk along the road, do not get too close to it.
• Carefully observe the possible exit of cars from yards, alleys.
• Do not play ball on the sidewalk, do not run.

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

These coloring pages will teach children the rules of safe use of public transport.

• A public transport stop is a dangerous place due to the possible poor visibility of the road and large crowds of people who can accidentally push a child off the sidewalk onto the roadway. Here you need to be especially careful.
• Approach the doors of the transport only after it has completely stopped.
• After leaving the vehicle, proceed to cross the road only after it has left the stop.

In addition to these basic rules of the road, children will be interested in coloring traffic signs. The presented coloring pages according to traffic rules are suitable for toddlers, preschoolers and students of primary school age, as well as for use in kindergartens and in lessons in primary school. All pictures with the Rules of the Road are completely free - they can be downloaded and printed.

(this entry 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 conjecture 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 (because my brain 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 an example. Imagine a map of the city, where at each intersection you can go in one of four directions - north, south, east and west. If the car starts at some intersection and follows some list of directions - "north, north, east", etc. - then she will eventually arrive at some other intersection. Is it possible to find such a list of directions, perhaps a long one, that will lead the car to the same place, regardless of where it started? 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 is stuck in a maze in which you need to find the center and called you asking for help. You know how the maze works, but you don't know where your friend is. Can there be a sequence of commands that will definitely lead your friend to the center, no matter where he is?

In these two examples, the "directions" at each point are fixed, and the solution either exists or it doesn't. But in a more general case, this problem asks: if we can choose where, for example, "west, north, east, south" points, at each intersection in its own way, can we then ensure the existence of a "synchronizing word" - a sequence of commands, which from 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. At the same time, a different number, not necessarily d, can enter each individual vertex. 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 "located" at some vertex, and we 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. A "word" is any sequence of letter-colors. Then, if a coloring is given in the graph, and x is some vertex and w is some word, then xw denotes the vertex we will arrive at, starting from x and following the word w.

The coloring book 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 asked by the road coloring problem is: is there always a synchronous coloring? Is it always possible to color the edges of a graph in such a way that all vertices can be reduced to one?

This problem has applications in several different areas, which can be read about, for example, on Wikipedia. For example, in computer science, in automata theory. A graph with a coloring can be thought of as a deterministic finite state machine in which the vertices are the states and the edges indicate how to navigate between them. Suppose we control this automaton from a distance, sending commands over some information channel, and due to some breakdowns, this channel was polluted, the automaton received some erroneous instructions, and now we don’t know what state it is in at all . 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 (besides the fact that each vertex has exactly d edges). First, the graph must be strongly connected, which means that there is a route from any vertex to any other. Second, the graph must not be periodic. Imagine that all graph vertices 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 cannot "jump" between any V either, 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 and what words you go, two vertices in different V i will never come together - they will go around the 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 conjecture in 1970, and since then there have been many partial results proving special cases, but a full proof appeared only in 2007. What follows is my retelling of almost the entire proof (except for one technical lemma).

Periodicity

First of all, let us replace the non-periodicity condition with another one that is equivalent to it. A graph is periodic if and only if there exists a number N>1 that divides the length of any cycle in the graph. Those. our requirement of non-periodicity is equivalent to saying 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 that satisfies 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're willing to take this on faith, you can easily skip the rest of this paragraph; it doesn't matter for the rest of the proof. If the graph is periodic, i.e. Since 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. Assume that there is such N>1, which divides the length of any cycle. Let's build in our graph some directed spanning tree (spanning tree) with a 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 claim that for any edge p-->q in the graph, l(q) = l(p) + 1 (mod N). If this statement is true, then it immediately follows from it that we can partition 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 mean the 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 condition, the lengths of these cycles are divisible by N, subtracting and canceling the total values, we obtain that l(p)+1 = l(q) mod N, which was to be proved.

Stable friendship and induction

Let some coloring of the graph G be given. We call two vertices p,q friends if some word w brings them to the same vertex: pw = qw. Let's call p,q enemies if they "never meet". Let's 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 can. Stable friends never become enemies.

The stability relation between vertices is, firstly, an equivalence (it is reflexive, symmetric, and transitive), and secondly, it is preserved by the graph structure: if p,q are stable friends, p is connected by an edge with p", q with q", and these edges the same color, then p" and q" are also stable friends. This means that stable friendship is congruence and it can be divided into: create a new graph G", whose vertices will be stable friendship equivalence classes in G. If there is at least one stable pair in G, then G" will be less than G in size. Moreover, if in the original graph G from each vertex has d edges, then in G" it will be the same. 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 on for each of the d colors.

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

Let's assume that in G" we managed to find a synchronizing coloring. It can now be used in G instead of the coloring with which we started: any edge p-->q will receive a new color according to the new color of the edge P-->Q. A little more precisely, we should say so: at each vertex P of the graph G" a new coloring is given by some permutation of all colors π P: the edge that was painted with color α gets 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. The new coloring of the graph G generally 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 - 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 of 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 on the way from p,q to the common vertex will be stable, i.e. lie inside the same vertex P n and therefore receive the same permutation π P n .

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

From all this it follows that in order to prove the theorem, it is enough to prove that in any graph that meets the conditions, there is a coloring in which there is a pair of stable friends . Because then it is possible to go from the graph G 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 be synchronizing for G .

Cliques and maximal sets

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

If the vertex set A has the form Gw for some w, and in addition any two vertices in A are enemies, i.e. 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 like this until there are only enemies left or only one vertex remains - also in this case a clique, just 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 containing x. This follows from the fact that there is some clique A (see the previous paragraph); if p is a vertex in it, then there is a word w leading from p to x, because connected graph; then Aw is a clique including x.

Clicks will help us to 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 for one in A and one in B, then these two vertices are stable friends. Thus, the problem reduces to finding a coloring that contains such cliques A and B.

In order to better understand how cliques work, it is useful to assign weights to vertices in a 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 that have edges in x, then we 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) on faith. If M is the matrix of the graph G (cell (i,j) is 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 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 come out of each vertex.

If A is any set of vertices, then w(A) denotes the sum of the weights of all vertices in 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 that you come to 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.

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

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 weight property from one vertex to the set of vertices A. If, in addition, moreover, A is the maximum set, then each of w(Aα -1) cannot be greater than w(A), because these sets also converge 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.

Let us have a set of maximal sets A 1 ...A n that do not intersect in pairs and are reduced to single vertices a 1 ...a n by the same word w (in the initial case there will be n=1 and only one set, so which is easy to start). 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 by 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 i h -1 w -1 go by the word whw to the final vertices a 1 ...a n , and the maximal set A 1 goes to some vertex Awhw = (Aw)hw = (a 1 h)w = xw. This vertex xw must also be different from all a 1 ...a n , because otherwise the maximum set A i could be completed with the 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 are all pairwise disjoint. We will continue this expansion until there are no vertices outside the set.

So we can cover the entire graph G with disjoint maximal sets. Since they are maximal, they all have the same total w max , and therefore their number in the coverage is 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 covering of N max maximal sets, each contains at most one member of A, so the size of A is at most N max . In particular, this is an upper limit on the size of any clique.

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 vertices of A. The number of terms, according to the previous paragraph, is at most N max , and each set aw -1 can be reduced to one point (to the point a with the word w), so its weight is not greater than the maximum w max . Since the whole sum is w(G) = N max *w max , we conclude that the number of terms is exactly N max , and each term is exactly w max . We have proved that all clicks 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 for one: |A| - |A∩B| = 1.

Since A and B have the same size, we also have |B| - |A∩B| = 1, i.e. A and B have all elements in 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 this is not the case, 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 again they have all the 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 elements of Aw are pairwise enemies, because it is a clique; the same is true of the elements Bw; and only a couple of pw, qw remained - also enemies. But this set has N max +1 elements, and above we showed that any set of pairwise enemies cannot have 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 cliques

Let us take all vertices from a given graph G, and choose only one outgoing edge from each vertex. Such a choice defines a subgraph, which we 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 the only choice, because in R only one edge comes out of each vertex, and sooner or later we will close cycle. Maybe this cycle will not close at x, but will close somewhere "further" - for example, x-->y-->z-->s-->y. Then from x will lead "tail" to this cycle. If we start from some other peak, we will also definitely come to a cycle - this one or some other one. It turns out that any vertex of R either lies on a cycle (of which there may 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 in a "root" that lies on one of the cycles.

To each vertex of the graph we can assign level, corresponding to its distance from the cycle in the given spanning graph R. Vertices that lie on the cycle have level 0, and vertices that lie on the tree attached to the cycle receive a level equal to the distance in their tree to the "root" lying on cycle. Some vertices of our graph have a maximum level L. Perhaps it is generally equal to 0 - i.e. there are no trees, only 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 one.

We want to choose a spanning graph R in such a way that all vertices of maximum level lie on the same tree. Intuitively, one can believe that this can be done, because if this is not the case - for example, they are scattered across different trees - then one can choose one of such maximum vertices x and increase its level by attaching to R some edge going to x. Then some other edge will have to be thrown out, and it's not certain that it won't hurt something else... but that's a technical issue, more on that later. I'm just trying to say that it doesn't intuitively look very complicated.

For the moment, suppose that we can choose R so that all vertices of maximum level lie in the same tree. This tree is assumed to be nontrivial, i.e. maximum level L > 0. Based on this assumption, we will construct a coloring with cliques A and B in it, satisfying the condition of the previous section, and this will prove that this coloring has a stable pair of friends.

The coloring will be as follows: we choose some color α, and we color all the edges in the graph R in this color, and all the 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 α "advance" 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 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 vertex of maximum level L? According to our assumption, all such vertices are in the same tree as x, which means that the word α L leads 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, apart from x, K can only include lower level vertices.

Let's look at the set A = Kα L-1 . This is also a clique, and in it all vertices, except for x, have reached some of their cycles in R, because all vertices of A, except for x, have a level less than L. Only x is still outside the cycle, at a distance of exactly 1 to its root on the cycle. 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 a 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 for x, lay on cycles, and therefore remained there 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 for one: |A| - |A∩B| = 1. But this just means, according to the previous section, that our coloring has a stable pair, which was to be proved.

Building the maximum level.

It remains to prove that it is always possible to choose a spanning graph R in such a way that it has a nontrivial maximum level L > 0, and all vertices of this level lie on the same tree.

Part of this proof is a rather boring and technical lemma that I have read and tested, but I won't rehash it, I'll just say where it is in the article for those who are interested. But I will tell you how to get to this lemma.

We will need two restrictions that we can impose on the graph G. First, we say that there are no loops in G, i.e. 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", we will color the edges so that the color α always leads to this vertex. Because the graph is connected, this is easy to arrange, and then the loop ensures that some power of α will bring the entire graph to this vertex.

Next, 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 links lead from different vertices p and q. Why can we impose it? Because if there are links from p and q to r, then for any coloring p,q will converge to the vertex r after the first color, and therefore they are stable friends. So in this case, we do not need all the construction of spanning graphs and cliques, 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 non-trivial trees. We choose some R, and suppose that all vertices in it lie on cycles. If in the graph G all the edges lay in bundles - i.e. always all d edges outgoing from one vertex led to the same vertex - then choosing R would involve just choosing one edge from each bundle. In this case, there could be only one cycle in R (after all, several cycles in R could not be connected to each other in a connected graph G - all edges of G connect only the same vertices as the edges of R, because these are ligaments - and since G is connected, this is impossible), and any cycle in G simply selects other edges from the links of this cycle, but in fact it is the same cycle, 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 in G all edges lie on ties, 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 with p-->s, and this will "break" the cycle, creating some non-trivial tail in it. This tail will give us a non-trivial tree in the new graph.

Now, from all the spanning graphs R that have non-trivial trees, we can choose some R that has the maximum number of vertices on the cycles. T.e. it has vertices not on cycles, but apart from this limitation, the number of vertices on cycles is maximized. This graph has some vertices of maximum level L, and we can assume that they are on trees leading to different roots, otherwise we have already achieved what we need. We 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 rest of the trees do not change, and then the maximum level will be in only one tree, which is what we want. You can change the graph in three ways:

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

Lemma 7 of Trachtman's article proves 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 a greater number of vertices on cycles than in R, 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 get a graph R in which all vertices of the maximum level lie on one non-trivial tree.

Update, a week later: nevertheless, I decided to make this entry completely self-sufficient and also 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 want to draw it or tear it out of the article, so I’ll try in words. So, let's imagine that we have a spanning graph R, which has non-trivial trees, and of all such graphs in it, the maximum number of vertices lies on cycles. We aim to transform R into a spanning graph in which all vertices of maximum level lie on the same tree; as soon as we get such a graph in the process of trying, we immediately finish (and we don’t care that the maximum graph in terms of the number of vertices on cycles can be lost, it is not important to us in 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 still some trees joining this cycle or others that have level L vertices - otherwise everything is already done. It follows that if we manage to get a tree from T with an element of greater degree than L, and not lengthen these other trees, then we are done.

First, let's try to perform operation a) above: take some edge y-->x in G - it exists, because the graph is connected and without loops, and does not lie in R, because x max level. Let's add it to R, and throw out some y-->z that was there before. If y lies on the tree T, then y-->x closes a new cycle, and in the new graph, more vertices lie on cycles, and there are still non-trivial 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 deleting y-->z does not break this cycle, and adding y-->x lengthens the maximum level of the tree T by at least one, and the others trees don't lengthen, so we're done. The remaining option is when y-->z lay on the cycle C, which has now broken, and a new cycle has 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, while 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, so 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, vertex z now 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 lies. If on the 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, while other trees will not, and we are done . If on another cycle, not C, then we will now do a) along with b) also a): since we know that y-->z lies on C, then this operation will break C, but not the new cycle to which it is now connected tree Τ, and this tree will now have vertices of a level greater than L, and we are done again.

The remaining option is 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 originally - tree T, node x of level L, etc. - only the tree is now connected to the cycle through the vertex d. Considering now operation a), we conclude (assuming 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) does not work, then any edge from b must lead to r, i.e. edges from b form a bundle.

Finally, consider the edge c-->r lying on the cycle C. Since we can assume that all edges from b lie on the link leading to r, we can also impose the constraint mentioned above that there cannot be two links , leading to one vertex, not all edges from c lead to r, but there is some edge c-->e. Let's replace c-->r with c-->e. Where can the vertex e lie? Not on the tree T, because that would "extend" the cycle C, contradicting the maximality of R. So e lies on a different tree, or on a different cycle, or even on the same cycle C, but not at the vertex r. Then the tree T, before it is connected to the cycle, is now extended by at least one edge outgoing from r, and maybe 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 vertex x and other maximal vertices T is now at least L + 1, and the other trees have not lengthened, and again we have what we need.