Because I solved a random problem using DFS tree recently.
There are \(1000\) cities in a country and there are some two-way roads between them such that there are at least one path of roads between each two cities. Prove that there exist \(90\) cities in this country such that the distance between each of the other cities to at least one of these \(90\) cities is equal or less than \(10\) (\(10\) roads).
A simple graph with \(n\) vertices and more than \(3(n-1)/2\) edges is given. Prove that two different vertices \(x\), \(y\) of \(G\) can be found, such that there exist \(3\) non-intersecting each other paths connecting \(x\) and \(y\). (Two paths connecting \(x\) and \(y\) are non-intersecting if they do not share a vertex different from \(x\) and \(y\).)
Let \(G\) be a simple graph with \(2n+1\) vertices and at least \(3n + 1\) edges. Prove that there exist a cycle having an even numbers of edges. Prove that this is not always true if the graph has only \(3n\) edges.
There are \(n \geq 3\) cities, that connected by roads. We can reach every city from another city. It is known, that if we close any cyclic route, then we cannot reach every city from another city. What is the maximum number of roads there can be?
A graph with \(n\ge 6\) vertices is given. Every vertex has degree at least \(3\). Let us enumerate all the cycles in this graph as \(C_1\), \(C_2\), \(\dots\), \(C_k\). Determine all possible values of \[d:= \gcd \left(|C_1|,|C_2|,\dots,|C_k| \right)\] where \(|C|\) denotes the length of a cycle \(C\).
In the city there are \(2019\) metro stations. Some pairs of stations are connected via tunnels, and from any station through the tunnels you can reach any other. The mayor ordered to organize several metro lines: each line should include several different stations connected in series by tunnels (several lines can pass through the same tunnel), and each station must lie at least on one line. To save money no more than \(k\) lines should be made. It turned out that the order of the mayor is not feasible. What is the largest \(k\) such that this happens?
Let \(n \ge 1\) be a given integer. Let \(G\) be a finite simple graph with the property that each of its edges is contained in at most \(n\) cycles. Prove that the chromatic number of the graph is at most \(n+1\).
Given any positive real number \(\varepsilon\), prove that, for all but finitely many positive integers \(v\), any graph on \(v\) vertices with at least \((1+\varepsilon)v\) edges has two distinct simple cycles of equal lengths. (Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.)
\(A_1\), \(A_2\), \(\dots\) is an infinite sequence of sets, each consisting of finitely many elements. For any finite number of them \(A_{n_1}\), \(A_{n_2}\), \(\dots\), \(A_{n_m}\) there exist pairwise distinct elements \(x_1\), \(x_2\), \(\dots\), \(x_m\) such that \(x_j \in A_{n_j}\), \(1 \leq j \leq m\). Prove that there exist pairwise distinct elements \(a_1\), \(a_2\), \(a_3\), \(\dots\) such that \(a_i \in A_i\), \(\forall i\in \mathbf{N}\).
Hint (Kőnig's lemma). Every infinite, locally finite graph has an infinite ray.
Prove that a graph \(G\) that is \(2\)-connected, and such that removing any two non-adjacent vertices of \(G\) makes it disconnected must be either complete or a cycle.
Let \(T\) be a tree with at least \(m^n\) vertices, \(m \ge 3\), \(n \ge 1\), and each vertex has degree at most \(m\). Prove that there exists a path with length at least \(2n\).
Given is a simple connected graph with \(2n\) vertices. Prove that its vertices can be colored with two colors so that if there are \(k\) edges connecting vertices with different colors and \(m\) edges connecting vertices with the same color, then \(k-m \geq n\).
Given an undirected graph \(G\) with \(|E|\geq |V|+4\) where \(E\), \(V\) are the sets of segments and vertices respectively. Prove that there exists two cycles sharing no common segment.
Let \(S\) be a set of \(N \ge 3\) points in the plane. Assume that no \(3\) points in \(S\) are collinear. The segments with both endpoints in \(S\) are colored in two colors. Prove that there is a set of \(N - 1\) segments of the same color which don't intersect except in their endpoints such that no subset of them forms a polygon with positive area.