Coloring book road. Traffic rules coloring pages. Cliques and maximal sets

You can keep boys busy for a long time if you invite them to play with cars in the sandbox. But what to do if it’s cold outside and the child is bored. In this case, you can download and print the following road templates for cars. 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 required number of required A4 sheets are printed.

Download straight road for cars

You will need the most of these sheets. On an A4 sheet of paper 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 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 there.

Road for cars: 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 in the road for cars

The following A4 template will help you turn the road at any radius.

Child's knowledge of the Rules traffic- one of the main conditions for his safety on the street. Many pedestrians, including adults, take these rules rather lightly, which often becomes the cause of traffic accidents of varying severity. Children must clearly understand that when they are on the street in a populated area, they are full participants in the road traffic, therefore compliance with traffic rules is their responsibility.

Coloring pages Traffic rules for children.

Teaching a child the rules of behavior on the street (roads, sidewalks, city transport) should begin in the 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 presented on this page are primarily intended for preschoolers and will help children learn the basic points of behavior on the road, as well as near it.

1. Coloring page Traffic light.

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

• Always start driving only when the traffic light is green.
• Never cross the road when traffic signals are red or yellow, even if there are no vehicles nearby.
• When turning to a green light, additionally make sure of your safety - look to the left, then to the right.

2. Coloring page pedestrian crossing.

Teach your child to cross roadway streets only at the 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 crossing.
• Before crossing the road, carefully inspect it and make sure that there is no traffic nearby.
• Cross the road, don't run across it.
• Don't cross the street diagonally.
• Pay special attention to stationary vehicles that block your view.
• When moving through a pedestrian crossing, stop talking on the phone.
• If there are underground or overpasses nearby, be sure to use them; traffic is especially intense in such places.

3. Sidewalks.

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

• When driving on the sidewalk along the road, do not get too close to it.
• Carefully monitor possible vehicles leaving courtyards and alleys.
• Don't play ball on the sidewalk or run.

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

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

• Stop public transport- a dangerous place due to a possible poor view of the road and a large crowd of people who could accidentally push a child off the sidewalk onto the roadway. Here you need to be especially careful.
• Approach the doors of the vehicle only after it has completely stopped.
• After getting out of the vehicle, proceed to cross the road only after it has left the stop.

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

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

The cars in the cartoon Cars live an ordinary life - one runs a tire store, the other a tuning studio, and some simply live for their own pleasure, like the hippie Fillmore (Volkswagen T1) or his friend, a World War II veteran. Serge (Willys). The main character of the film, McQueen, nicknamed “Lightning,” dreams only of racing, victories and glory. Once in the Radiator District on the famous American Highway 66, the still “green” McQueen immediately tells everyone how fast and cool he is. However, his first start in a NASCAR race dispels his illusions. Friends help the hero survive the loss - 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 would we be without the romantic beauty Sally (Porsche with a charming 911 tattoo)! Largely thanks to them, McQueen will still win the race, defeating Chico's main rival (Plymouth Hemi Cuda). Luigi's dream will also come true - one day a “stallion from Maranello”, voiced, by the way, by the “Red Baron” himself, Michael Schumacher, will come to his shop to change tires.

It is noteworthy that both the creators of the film and those who voiced it are people involved in cars. For example, director Joe Lasseter spent almost his entire childhood at the Chevrolet plant, where his father was one of the chief designers. Ford's leading designer Jay Mays 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 characters.

Only the original noise of the cars was used - 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 film, 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 an antique Ford T.

(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 proven by Israeli mathematician Abraham Trachtman. The proof turned out to be quite elementary, and with some difficulties (since my brains had atrophied) I was able to read and understand it, and I will even try to explain it in this post.

The problem can be explained with the following example. Imagine a city map on which at each intersection you can go in one of four directions - north, south, east and west. If the car starts from some intersection and follows some list of instructions - “north, north, east”, etc. - then she will eventually arrive at some other intersection. Is it possible to find a list of directions, possibly long, that will lead the machine to the same place no matter where it starts? If the map looks like Manhattan - a regular grid - then no, but maybe it has a lot of dead ends and unexpected turns?

Or another example. Your friend is stuck in a maze in which he needs to find the center, and he called you asking 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 a solution either exists or it doesn't. But more generally, this problem asks: if we can choose where, for example, "west, north, east, south" points at each intersection differently, 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 uniform outdegree d - this means that each vertex has exactly d edges. In this case, each individual vertex can be entered different quantities, optional d. Let us have a set of d letters of some alphabet, which we will call “colors”. Then the “coloring” of the graph is given by assigning for each vertex all d letters for its d 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. A “word” is any sequence of letters-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 to which we will arrive 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 synchronizing word. The question asked by the road coloring problem is: is there always a synchronizing 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 on Wikipedia for example. Let's say, in computer science, in automata theory. A coloring graph can be thought of as a deterministic finite automaton, in which the vertices are states and the edges indicate how to move between them. Suppose we control this machine at a distance, sending commands through some information channel, and due to some breakdowns this channel was contaminated, the machine received some erroneous instructions, and now we don’t even know what state it is in . Then, if there is a sync word, we can bring it to a known state, regardless of 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). Firstly, the graph must be strongly connected - this means that there is a route from any vertex to any other. Secondly, the graph must not be periodic. Let's 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 Vi and Vi+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 it and no matter what words you use, two vertices in different V i will never come together - 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 special cases, but the full proof did not appear until 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 equivalent one. A graph is periodic if and only if there is a number N>1 by which the length of any cycle in the graph is divided. Those. our non-periodicity requirement 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 that satisfies this condition has a synchronizing coloring.

Proving that periodicity is equivalent to the condition “there is N>1 by which the length of any cycle is divided” 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. can divide the vertices into sets V 1, V 2, ... V n, so that the edges go between them along a cycle, then it is obvious that the length of any cycle must be divisible by n, i.e. the new condition is satisfied. This is a trivial direction, but for our replacement we need just the second direction. Suppose that there is N>1, by which the length of any cycle is divided. Let's build some directed spanning tree in our graph with the root at vertex r. To any vertex x there is a route in this tree starting from the root of length l(x). We now claim that for any edge p-->q in the graph it holds that l(q) = l(p) + 1 (mod N). If this statement is true, then it immediately follows 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 the spanning tree, then this is obvious, because then simply 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 Rq. 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 condition, the lengths of these cycles are divided by N, subtracting and reducing the total values, we obtain that l(p)+1 = l(q) mod N, which is what needed to be proved.

Stable friendship and induction

Let a certain coloring of the graph G be given. Let us 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 get together.” 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 come. Stable friends will never become enemies.

The stability relation between vertices is, firstly, equivalence (it is reflexive, symmetric and transitive), and secondly preserved by the structure of the graph: if p, q are stable friends, p is connected by an edge to p, q to q", and these edges same color, then p" and q" are also stable friends. This means that a stable friendship is congruence and can be divided by: create a new graph G", the vertices of which will be equivalence classes for stable friendships in G. If there is at least one stable pair in G, then G" will be smaller than G. Moreover, if in the original graph G from each vertices had d edges, then in G" this will be the case. For example, if P is a vertex of the 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 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 also so. After all - using our alternative definition of periodicity - any cycle in G turns into a cycle in G", so if all the lengths of the cycles 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 we managed to find a synchronizing coloring in G. 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. It should be a little more precise 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 colored with color α receives a new color π P (α). Then in the original graph G, at each vertex p from the stability class P we use the same permutation π P to recolor its edges. Generally speaking, a new coloring of the graph G defines some new concepts of “friendship”, “enmity” and “stability”, which 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 “translated” from the old coloring to the new one or vice versa, using the permutation π P at each vertex p along the way. 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, i.e. lie inside one 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 will converge somewhere "inside P". As stated above, all vertices within the class P remain stable in the new coloring, which means that we can now continue w, again and again bringing together the remaining still separate pairs of vertices 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 from graph G we can go to graph G" of smaller size, and it also meets all the conditions. Using an 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 vertices in a graph and a 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 vertices of the graph in general, then we denote this by Gw. In this notation, a synchronizing coloring means that there is w such that Gw is a set of one element.

If the set of vertices A has the form Gw for some w, and in addition, any two vertices in A are enemies, i.e. will never converge, let's call A clique. Cliques exist because we can always start with the whole G, take a pair of friend vertices, traverse the w that connects them, and reduce the number of vertices by one; continue this way until only enemies remain or only one vertex remains - also in this case 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 including x. This follows from the fact that there is some kind of clique A (see 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 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, such that all the vertices in them are common except one in A and one in B, then these two vertices are stable friends. Thus, the problem reduces to finding a coloring that contains cliques A and B.

To better understand how cliques work, it is 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, such that if for any vertex x sum the weights of all vertices from which there are 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) for granted. If M is a matrix of a 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 has for the eigenvalue d. We know 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 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 her in the appropriate color.

Let us now consider all the sets of vertices that can be brought together to one point, i.e. such A that for some w Aw contains only one vertex. Those sets A that among all such sets have the maximum weight w(A) will be called maximal sets. If the coloring is synchronizing, then the entire 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 over all d colors, is equal to d*w(A) - this is simply a generalization of the main property of weight from one vertex to the set of vertices A. If, in addition, in this case A is a maximal set, then each of w(Aα -1) cannot be greater than w(A), because these sets are also reduced 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. It immediately follows that if A is maximal, then Aw -1 is also maximal for any word w.

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

Let us have a set of maximal sets A 1 ...A n , disjoint in pairs, and 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 that it's easy to start). It is clear that all a 1 ...a n are different from each other, because otherwise it would be possible to further expand the maximum set due to the elements of another with the same final vertex. Suppose that all A i together have not yet exhausted all the 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 according to 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 differ from all a 1 ...a n , because otherwise the maximal set A i could be supplemented 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 are all pairwise disjoint. We will continue this expansion until there are no vertices left outside the set.

So we can cover the entire graph G with disjoint maximal sets. Since they are maximal, they all have the same entire 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). A maximal set cannot contain a pair of enemies, because then it could not converge. This means that in a covering of N max maximal sets, each contains at most one member A, so the size of A is at most N max . Specifically, it 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 the vertices of A. The number of terms, according to the previous paragraph, is no more than N max, and each set aw -1 can be reduced to one point (at point a with the word w), so its weight is not greater 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 have proven that all cliques have the same size: exactly N max elements.

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

Since A and B are 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 so, 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 of Aw are pairwise enemies, because it is a clique; the same is true for the Bw elements; and only the pair 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 of any w. In other words, p and q are stable friends.

Spanning graphs and cliques

Let us take all the vertices from a given graph G, and select only one outgoing edge from each vertex. This choice determines 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 what they look like. Let there be a certain spanning graph R. If we take any vertex x in it and start following its edges, then each time we will have a single 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 will close somewhere “further” - for example, x-->y-->z-->s-->y. Then the “tail” to this cycle will lead from x. If we start from some other vertex, we will also definitely end up with a cycle - this one or some other one. It turns out that any vertex R either lies on a cycle (of which there can be several), or is part of the “tail” that leads to a 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 the “root”, which lies on one of the cycles.

We can assign to each vertex of the graph level, corresponding to its distance to the cycle in a 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 even equal to 0 - i.e. 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 one.

We want to choose a spanning graph R such that all vertices of the maximum level lay 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 maximal vertices x and increase its level by attaching to R some edge going to x. Then some other rib will have to be thrown out, and it’s not a fact that this will not harm something else... but this is a technical issue, which will be discussed later. I'm just trying to say that it doesn't seem very complicated intuitively.

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

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

Let x be any vertex of maximal level L in R, and let K be any clique including x; we know that such a clique exists. Can K include some other vertex 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 takes them to the same place as x - namely, to the root of this tree, which lies on the cycle. This means that all such vertices are friends of x, and therefore cannot lie in the same clique as it. Therefore, besides x, K can only include vertices of a lower level.

Let's look at the set A = Kα L-1. This is also a clique, and in it all the vertices, except x, have reached some kind of cycle in R, because all the vertices of A, except x, have a level less than L. Only x remains 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 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, lay on cycles, and therefore remained there in B; and only x finally entered its cycle and settled down there somewhere. This means that the intersection of A and B contains all 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 needed to prove.

Building the maximum level.

It remains to prove that it is always possible to choose a spanning graph R such 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, which I read and checked, but I won’t repeat it, I’ll just say where it is in the article for those who are interested. But I’ll tell you how to get to this lemma.

We will need two restrictions that we can impose on the graph G. First, let's say that G has no loops, 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 a synchronizing coloring in another way. Let's color this loop some color α, and then, going from this vertex in the opposite direction "against the arrows", color the edges so that color α always leads to this vertex. Because the graph is connected, this is easy to arrange, and then the loop ensures that some degree α will reduce 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 bunch. Our second constraint is this: there is no vertex r to which two links from different vertices p and q lead. Why can we impose it? Because if from p and q there are connections in r, then for any p,q coloring will converge at vertex r after the first color, and therefore they are stable friends. So in this case we don't 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, we prove that there always exists a spanning graph R in which not all vertices lie on cycles, but there are some non-trivial trees. Let's choose some R and assume that all its vertices lie on cycles. If all the edges in graph G were connected, i.e. always all d edges leaving the same vertex led to the same vertex - then the choice of R would involve just choosing one edge from each link. In this case, there could be only one cycle in R (after all, several cycles in R could not possibly 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 since G is connected, this is impossible), and any cycle in G simply selects other edges from the connections of this cycle, but in essence 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 precisely contradicts the non-periodicity of G. Therefore, it cannot be that all the edges in G lie on links, 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 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 that contain nontrivial trees some R that has the maximum number of vertices on cycles. That is it has vertices that are not on cycles, but besides this limitation, the number of vertices on cycles is maximized. There are some vertices of the maximum level L in this graph, and we can assume that they are on the 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 want. You can change the graph in three ways:

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 throw it away, 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 Trakhtman's paper proves in detail that one (or in some case two) of these changes leads 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 links lead. As a result, in any case, we obtain a graph R in which all the vertices of the maximum level lie on one non-trivial tree.

Update, a week later: I nevertheless 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 rip it out of the article, so I’ll try with words. So, imagine that we have a spanning graph R, in which there are non-trivial trees, and of all such graphs in it, the maximum number of vertices lie on cycles. We aim to transform R into a spanning graph in which all vertices of the 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 maximality of the graph in terms of the number of vertices on cycles may 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 some other trees joining this cycle or others that have vertices of level L - otherwise everything has already been done. It follows that if we can get from T a tree with an element of greater degree than L, and not extend 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, because The graph is connected and without loops, and does not lie in R, because x maximum level. Let's add it to R, and throw out 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 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 a cycle C, then removing y-->z does not break this cycle, but adding y-->x extends the maximum level of the tree T by at least one, and others the trees don't lengthen, so we're done. The remaining option is when y-->z lay on 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, 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, 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 a tree T, then we created a new cycle without breaking the previous one, and disproved the maximality of R. If on another tree, then the maximal vertices of T, including x, will now have a level greater than L, and the 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 it is now connected tree T, and on this tree there will now be vertices of a level greater than L, and we are finished again.

The remaining option is when b-->d is also connected to 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. - only the tree is now connected to the cycle through vertex d. Considering now operation a), we conclude (assuming that it does not work) that l(zd) = L, just as we previously concluded 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. the edges from b form a link.

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 vertex e lie? Not on tree T, because that would "extend" the cycle C, contradicting the maximality of R. So e lies on another tree or on another cycle, or even on the same cycle C, but not at vertex r. Then the tree T, before it joins the loop, is now extended by at least one edge emanating from r, and maybe by more (only by one if e lies immediately after r, and c-->e closes the loop C again, deriving only r from it). This means that vertex x and other maximal vertices T now have a level no less than L+1, and other trees have not lengthened, and again we got what we need.