There are $2024$ cities in a country, every two of which are bidirectionally connected by exactly one of three modes of transportation - rail, air, or road. A tourist has arrived in this country and has the entire transportation scheme. He chooses a travel ticket for one of the modes of transportation and the city from which he starts his trip. He wants to visit as many cities as possible, but using only the ticket for the specified type of transportation. What is the largest $k$ for which the tourist will always be able to visit at least $k$ cities? During the route, he can return to the cities he has already visited. [i]Proposed by Bogdan Rublov[/i]

In a graph with $8$ vertices that contains no cycle of length $4$, at most how many edges can there be?

In the Cartesian plane, let $G_1$ and $G_2$ be the graphs of the quadratic functions $f_1(x) = p_1x^2 + q_1x + r_1$ and $f_2(x) = p_2x^2 + q_2x + r_2$, where $p_1 > 0 > p_2$. The graphs $G_1$ and $G_2$ cross at distinct points $A$ and $B$. The four tangents to $G_1$ and $G_2$ at $A$ and $B$ form a convex quadrilateral which has an inscribed circle. Prove that the graphs $G_1$ and $G_2$ have the same axis of symmetry.

Let $n$ and $k$ be positive integers. A simple graph $G$ does not contain any cycle whose length be an odd number greater than $1$ and less than $ 2k + 1$. If $G$ has at most $n + \frac{(k-1) (n-1) (n+2)}{2}$ vertices, prove that the vertices of $G$ can be painted with $n$ colors in such a way that any edge of $G$ has its ends of different colors.

Determine all graphs $G$ with the following two properties: $\bullet$ G contains at least one Hamilton path. $\bullet$ For any pair of vertices, $u, v \in G$, if there is a Hamilton path from $u$ to $v$ then the edge $uv$ is in the graph $G$

Bertalan thought about a $4$-digit positive number. Then he draw a simple graph on $4$ vertices and wrote the digits of the number to the vertices of the graph in such a way that every vertex received exactly the degree of the vertex. In how many ways could he think about? In a simple graph every edge connects two different vertices, and between two vertices at most one edge can go.

Given a graph with $n$ ($n\ge 4$) vertices . It is known that for any two vertices $A$ and $B$ there exists a vertex which is connected by edges both with $A$ and $B$. Find the smallest possible numbers of edges in the graph. E. Barabanov

The country has $n \ge 3$ airports, some pairs of which are connected by bidirectional flights. Every day, the government closes the airport with the strictly highest number of flights going out of it. What is the maximum number of days this can continue? [i]Proposed by Fedir Yudin[/i]

A boa of size $k$ is a graph with $k+1$ vertices $\{0,1,\dots,k-1,k\}$ and edges only between the vertices $i$ and $i+1$ for $0\leq i < k.$ The boa is place in a graph $G$ through a injection of graphs. (This is an injective function form the vertices of the boa to the vertices of the graph in such a way that if there is an edge between the vertices $x$ and $y$ in the boa then there must be an edge between $f(x)$ and $f(y)$ in $G$). The Boa can move in the graph $G$ using to type of movement each time. If the boa is initially on the vertices $f(0),f(1),\dots,f(k)$ then it moves in one of the following ways: (i) It choose $v$ a neighbor of $f(k)$ such that $v\not\in\{f(0),f(1),\dots,f(k-1)\}$ and the boa now moves to $f(0),f(1),\dots,f(k)$ with $f'(k)=v$ and $f'(i) = f(i+1)$ for $0 \leq i < k,$ or (ii) It choose $v$ a neighbor of $f(0)$ such that $v\not\in\{f(1),f(2),\dots,f(k)\}$ and the boa now moves to $f(0),f(1),\dots,f(k)$ with $f'(0)=v$ and $f'(i) = f'(i-1)$ for $0 < i \leq k.$ Prove that if $G$ is a connected graph with diameter $d$, then it is possible to put a size $\lceil d/2 \rceil$ boa in $G$ such that the boa can reach any vertex of $G$.

Let $G$ be a bipartite graph in which the greatest degree of a vertex is 2019. Let $m$ be the least natural number for which we can color the edges of $G$ in $m$ colors so that each two edges with a common vertex from $G$ are in different colors. Show that $m$ doesn’t depend on $G$ and find its value.

A graph $G$ has $n + k$ vertices. Let $A$ be a subset of $n$ vertices of the graph $G$, and $B$ be a subset of other $k$ vertices. Each vertex of $A$ is joined to at least $k - p$ vertices of $B$. Prove that if $np < k$ then there is a vertex in $B$ that can be joined to all vertices of $A$.

We say that a graph $G$ is [i]divisive[/i], if we can write a positive integer on each of its vertices such that all the integers are distinct, and any two of these integers divide each other if and only if there is an edge running between them in $G$. Which Platonic solids form a divisive graph? [img]https://cdn.artofproblemsolving.com/attachments/1/5/7c81439ee148ccda09c429556e0740865723e0.png[/img]

* Let $A, B, C$ be three nodes of a graph paper. Prove that if $\vartriangle ABC$ is an acute one, then there is at least one more node either inside $\vartriangle ABC$ or on one of its sides.

Let a complete oriented graph on $n$ points be given. Show that the vertices can be enumerated as $v_1 , v_2 ,\ldots, v_n$ such that $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n.$

For each $a$, $1<a<2$, the graphs of functions $y=1-|x-1|$ and $y=|2x-a|$ determine a figure. Prove that the area of this figure is less than $\frac13$.

Show that the edges of a connected simple (no loops and no multiple edges) finite graph can be oriented so that the number of edges leaving each vertex is even if and only if the total number of edges is even

In the Cartesian plane, let $G_1$ and $G_2$ be the graphs of the quadratic functions $f_1(x) = p_1x^2 + q_1x + r_1$ and $f_2(x) = p_2x^2 + q_2x + r_2$, where $p_1 > 0 > p_2$. The graphs $G_1$ and $G_2$ cross at distinct points $A$ and $B$. The four tangents to $G_1$ and $G_2$ at $A$ and $B$ form a convex quadrilateral which has an inscribed circle. Prove that the graphs $G_1$ and $G_2$ have the same axis of symmetry.

Given distinct positive integers \( g \) and \( h \), let all integer points on the number line \( OX \) be vertices. Define a directed graph \( G \) as follows: for any integer point \( x \), \( x \rightarrow x + g \), \( x \rightarrow x - h \). For integers \( k, l (k < l) \), let \( G[k, l] \) denote the subgraph of \( G \) with vertices limited to the interval \([k, l]\). Find the largest positive integer \( \alpha \) such that for any integer \( r \), the subgraph \( G[r, r + \alpha - 1] \) of \( G \) is acyclic. Clarify the structure of subgraphs \( G[r, r + \alpha - 1] \) and \( G[r, r + \alpha] \) (i.e., how many connected components and what each component is like).

There is a population $P$ of $10000$ bacteria, some of which are friends (friendship is mutual), so that each bacterion has at least one friend and if we wish to assign to each bacterion a coloured membrane so that no two friends have the same colour, then there is a way to do it with $2021$ colours, but not with $2020$ or less. Two friends $A$ and $B$ can decide to merge in which case they become a single bacterion whose friends are precisely the union of friends of $A$ and $B$. (Merging is not allowed if $A$ and $B$ are not friends.) It turns out that no matter how we perform one merge or two consecutive merges, in the resulting population it would be possible to assign $2020$ colours or less so that no two friends have the same colour. Is it true that in any such population $P$ every bacterium has at least $2021$ friends?

Fix an integer $n \ge 2$, let $Q_n$ be the graph consisting of all vertices and all edges of an $n$-cube, and let $T$ be a spanning tree in $Q_n$. Show that $Q_n$ has an edge whose adjunction to $T$ produces a simple cycle of length at least $2n$.

There are n boys and m girls at Daehan Mathematical High School. Let $d(B)$ a number of girls who know Boy $B$ each other, and let $d(G)$ a number of boys who know Girl $G$ each other. Each girl knows at least one boy each other. Prove that there exist Boy $B$ and Girl $G$ who knows each other in condition that $\frac{d(B)}{d(G)}\ge\frac{m}{n}$.

Given is a natural number $n>4$. There are $n$ points marked on the plane, no three of which lie on the same line. Vasily draws one by one all the segments connecting pairs of marked points. At each step, drawing the next segment $S$, Vasily marks it with the smallest natural number, which hasn't appeared on a drawn segment that has a common end with $S$. Find the maximal value of $k$, for which Vasily can act in such a way that he can mark some segment with the number $k$?

Let $m$ and $n$ be positive integers. In Philand, the Kingdom of Olymphics, with $m$ cities, and the Kingdom of Mathematicians for Fun, with $n$ cities, fight a battle in rounds. Some cities in the country are connected by roads, so that it is possible to travel through all the cities via the roads. In each round of the battle, if all cities neighboring, that is, connected directly by a road, a city in one of the kingdoms are from the other kingdom, that city is conquered in the next round and switches to the other kingdom. Knowing that between the first and second round, at least one city is not conquered, show that at some point the battle must end, i.e., no city can be captured by another kingdom.

Given a graph with $99$ vertices and degrees in $\{81,82,\dots,90\}$, prove that there exist $10$ vertices of this graph with equal degrees and a common neighbour. [i]Proposed by Alireza Alipour[/i]

In a summer camp about Applied Maths, there are $8m+1$ boys (with $m > 5$) and some girls. Every girl is friend with exactly $3$ boys and for any $2$ boys, there is exactly $1$ girl who is their common friend. Let $n$ be the greatest number of girls that can be chosen from the camp to form a group such that every boy is friend with at most $1$ girl in the group. Prove that $n \geq 2m+1$.