Let the vertex set \( V \) of a graph be partitioned into \( h \) parts \( (V = V_1 \cup V_2 \cup \cdots \cup V_h) \), with \(|V_1| = n_1, |V_2| = n_2, \ldots, |V_h| = n_h \). If there is an edge between any two vertices only when they belong to different parts, the graph is called a complete \( h \)-partite graph, denoted as \( k(n_1, n_2, \ldots, n_h) \). Let \( n \) and \( r \) be positive integers, \( n \geq 6 \), \( r \leq \frac{2}{3}n \). Consider the complete \( r + 1 \)-partite graph \( k\left(\underbrace{1, 1, \ldots, 1}_{r}, n - r\right) \). Answer the following questions: 1. Find the maximum number of disjoint circles (i.e., circles with no common vertices) in this complete \( r + 1 \)-partite graph. 2. Given \( n \), for all \( r \leq \frac{2}{3}n \), find the maximum number of edges in a complete \( r + 1 \)-partite graph \( k(1, 1, \ldots, 1, n - r) \) where no more than one circle is disjoint.

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?

Two sequences $b_i$, $c_i$, $0 \le i \le 100$ contain positive integers, except $c_0=0$ and $b_{100}=0$. Some towns in Graphland are connected with roads, and each road connects exactly two towns and is precisely $1$ km long. Towns, which are connected by a road or a sequence of roads, are called [i]neighbours[/i]. The length of the shortest path between two towns $X$ and $Y$ is denoted as [i]distance[/i]. It is known that the greatest [i]distance[/i] between two towns in Graphland is $100$ km. Also the following property holds for every pair $X$ and $Y$ of towns (not necessarily distinct): if the [i]distance[/i] between $X$ and $Y$ is exactly $k$ km, then $Y$ has exactly $b_k$ [i]neighbours[/i] that are at the [i]distance[/i] $k+1$ from $X$, and exactly $c_k$ [i]neighbours[/i] that are at the [i]distance[/i] $k-1$ from $X$. Prove that $$\frac{b_0b_1 \cdot \cdot \cdot b_{99}}{c_1c_2 \cdot \cdot \cdot c_{100}}$$ is a positive integer.

On a table there are $100$ red and $k$ white buckets for which all of them are initially empty. In each move, a red and a white bucket is selected and an equal amount of water is added to both of them. After some number of moves, there is no empty bucket and for every pair of buckets that are selected together at least once during the moves, the amount of water in these buckets is the same. Find all the possible values of $k$.

In a small city there are $n$ bus routes, with $n > 1$, and each route has exactly $4$ stops. If any two routes have exactly one common stop, and each pair of stops belongs to exactly one route, find all possible values of $n$.

A graph is called 2-connected if after removing any vertex the remaining graph is still connected. Prove that for any 2-connected graph with degrees more than two, one can remove a vertex so that the remaining graph is still 2-connected.

On the Alphamegacentavra planet there are $2023$ cities, some of which are connected by non-directed flights. It turned out that among any $4$ cities one can find two with no flight between them. Find the maximum number of triples of cities such that between any two of them there is a flight.

A graph has $100$ points. Given any four points, there is one joined to the other three. Show that one point must be joined to all $99$ other points. What is the smallest number possible of such points (that are joined to all the others)?

We call a graph symmetric, if we can put its vertices on the plane such that if the edges are segments, the graph has a reflectional symmetry with respect to a line not passing through its vertices. Find the least value of $K$ such that the edges of every graph with $100$ vertices, can be divided into $K$ symmetric subgraphs.

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$.

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.

There are $2019$ coins on a table. Some are placed with head up and others tail up. A group of $2019$ persons perform the following operations: the first person chooses any one coin and then turns it over, the second person choses any two coins and turns them over and so on and the $2019$-th person turns over all the coins. Prove that no matter which sides the coins are up initially, the $2019$ persons can come up with a procedure for turning the coins such that all the coins have smae side up at the end of the operations.

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]

Let $n$ be a positive integer and let $G$ be a simple undirected graph on $n$ vertices. Let $d_i$ be the degree of its $i$-th vertex, $i = 1, \dots , n$. Denote $\Delta=\max d_i$. Prove that if \[\sum_{i=1}^n d_i^2>n\Delta(n-\Delta),\] then $G$ contains a triangle.

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.

A graph has $n$ points and $\frac{n(n-1)}{2}$ edges. Each edge is colored with one of $k$ colors so that there are no closed monochrome paths. What is the largest possible value of $n$ (given $k$)?

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 round-robin tournament with $n$ players in which there are no draws, the numbers of wins scored by the players are $s_1 , s_2 , \ldots, s_n$. Prove that a necessary and sufficient condition for the existence of three players $A,B,C$ such that $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$ is $$s_{1}^{2} +s_{2}^{2} + \ldots +s_{n}^{2} < \frac{(2n-1)(n-1)n}{6}.$$

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$?

Given a positive integer number $n$, determine the maximum number of edges a triangle-free Hamiltonian simple graph on $n$ vertices may have.

Let $G$ be a simple graph with $n$ vertices and $m$ edges. Two vertices are called [i]neighbours[/i] if there is an edge between them. It turns out the $G$ does not contain any cycles of length from 3 to $2k$ (inclusive), where $k\geq2$ is a given positive integer. a) Prove that it is possible to pick a non-empty set $S$ of vertices of $G$ such that every vertex in $S$ has at least $\left\lceil \frac mn \right\rceil$ neighbours that are in $S$. ($\lceil x\rceil$ denotes the smallest integer larger than or equal to $x$.) b) Suppose a set $S$ as described in (a) is chosen. Let $H$ be the graph consisting of the vertices in $S$ and the edges between those vertices only. Let $v$ be a vertex of $H$. Prove that at least $\left\lceil \left(\frac mn -1\right)^k \right\rceil$ vertices of $H$ can be reached by starting at $v$ and travelling across the edges of $H$ for at most $k$ steps. (Note that $v$ itself satisfies this condition, since it can be reached by starting at $v$ and travelling along the edges of $H$ for 0 steps.)

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).

Edges of a planar graph $G$ are colored either with blue or red. Prove that there is a vertex like $v$ such that when we go around $v$ through a complete cycle, edges with the endpoint at $v$ change their color at most two times. Clarifications for complete cycle: If all the edges with one endpoint at $v$ are $(v,u_1),(v,u_2),\ldots,(v,u_k)$ such that $u_1,u_2,\ldots,u_k$ are clockwise with respect to $v$ then in the sequence of $(v,u_1),(v,u_2),\ldots,(v,u_k),(v,u_1)$ there are at most two $j$ such that colours of $(v,u_j),(v,u_{j+1})$ ($j \mod k$) differ.

Prove that the number of orientations of a connected $3$-regular graph on $2n$ vertices where the number of vertices with indegree $0$ and outdegree $0$ are equal, is exactly $2^{n+1}$ $ {2n} \choose {n}$.

Draw the graph of the function $y = \frac{| x^3 - x^2 - 2x | }{3} - | x + 1 |$.