Show that, for every integer $r \ge 2$, there exists an $r$-chromatic simple graph (no loops, nor multiple edges) which has no cycle of less than $6$ edges

Let a set $X$ be given which consists of $2 \cdot n$ distinct real numbers ($n \geq 3$). Consider a set $K$ consisting of some pairs $(x, y)$ of distinct numbers $x, y \in X$, satisfying the two conditions: [b]I.[/b] If $(x, y) \in K$ then $(y, x) \not \in K$. [b]II.[/b] Every number $x \in X$ belongs to at most 19 pairs of $K$. Show that we can divide the set $X$ into 5 non-empty disjoint sets $X_1, X_2, X_3, X_4, X_5$ in such a way that for each $i = 1, 2, 3, 4, 5$ the number of pairs $(x, y) \in K$ where $x, y$ both belong to $X_i$ is not greater than $3 \cdot n$.

The complete graph with 6 points and 15 edges has each edge colored red or blue. Show that we can find 3 points such that the 3 edges joining them are the same color.

The $\underline{\text{path number}}$ of a graph is the minimum number of paths we need to partition the vertices of a graph. Given a connected graph with the independence number $k > 1$, what is the maximum possible value for the path number in this graph? Find the answer in terms of $k$. The independence number of a graph $\textbf{G}$ is the maximum possible number $k$, such that there exist $k$ pairwise non-adjacent vertices in $\textbf{G}$.

A hilly island has $2023$ lookouts. It is known that each of them is in line of sight with at least $42$ of the other lookouts. For any two distinct lookouts $X$ and $Y$ there is a positive integer $n$ and lookouts $A_1,A_2,\dots,A_{n+1}$ such that $A_1=X$ and $A_{n+1}=Y$ and $A_1$ is in line of sight with $A_2$, $A_2$ with $A_3$, $\dots$ and $A_n$ with $A_{n+1}$. The smallest such number $n$ is called the [i]viewing distance[/i] of $X$ and $Y$. Determine the largest possible viewing distance that can exist between two lookouts under these conditions.

In some foreign country's government, there are 12 ministers. Each minister has 5 friends and 6 enemies in the government (friendship/enemyship is a symmetric relation). A triplet of ministers is called [b]uniform[/b] if all three of them are friends with each other, or all three of them are enemies. How many uniform triplets are there?

In Tigre there are $2024$ islands, some of them connected by a two-way bridge. It is known that it is possible to go from any island to any other island using only the bridges (possibly several of them). In $k$ of the islands there is a flag ($0 \le k \le 2024$). Ana wants to destroy some of the bridges in such a way that after doing so, the following two conditions are met: \\ $\bullet$ If an island has a flag, it is connected to an odd number of islands. \\ $\bullet$ If an island does not have a flag, it is connected to an even number of islands. \\ Determine all values of $k$ for which Ana can always achieve her objective, no matter what the initial bridge configuration is and which islands have a flag.

Let $ n$ and $ k$ be positive integers such that $ \frac{1}{2} n < k \leq \frac{2}{3} n.$ Find the least number $ m$ for which it is possible to place $ m$ pawns on $ m$ squares of an $ n \times n$ chessboard so that no column or row contains a block of $ k$ adjacent unoccupied squares.

Given positive integers $n,k$, $n \ge 2$. Find the minimum constant $c$ satisfies the following assertion: For any positive integer $m$ and a $kn$-regular graph $G$ with $m$ vertices, one could color the vertices of $G$ with $n$ different colors, such that the number of monochrome edges is at most $cm$.

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

There are $n\geq 2$ people at a meeting. Show that there exist two people at the meeting who have the same number of friends among the persons at the meeting. (It is assumed that if $A$ is a friend of $B,$ then $B$ is a friend of $A;$ moreover, nobody is his own friend.)

A round-robin tournament among $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?

Given a natural number $k> 1$. Prove that if through any edge of the graph $G$ passes less than $[e(k-1)! - 1]$ simple cycles, then the vertices of this graph can be colored with $k$ colors in the correct way.

Let $n$ be a natural number. The graph $G$ has $10n$ vertices. They are separated into $10$ groups with $n$ vertices and we know that there is an edge between two of them if and only if they belong to two different groups. What’s the greatest number of edges a subgraph of $G$ can have, so that there are no 4-cliques in it?

We consider a prism which has the upper and inferior basis the pentagons: $A_{1}A_{2}A_{3}A_{4}A_{5}$ and $B_{1}B_{2}B_{3}B_{4}B_{5}$. Each of the sides of the two pentagons and the segments $A_{i}B_{j}$ with $i,j=1,\ldots$,5 is colored in red or blue. In every triangle which has all sides colored there exists one red side and one blue side. Prove that all the 10 sides of the two basis are colored in the same color.

At a party, $25$ elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves. Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group.

Let $d_1, d_2, \ldots, d_n$ be given integers. Show that there exists a graph whose sequence of degrees is $d_1, d_2, \ldots, d_n$ and which contains an perfect matching if, and only if, there exists a graph whose sequence of degrees is $d_2, d_2, \ldots, d_n$ and a graph whose sequence of degrees is $d_1-1, d_2-1, \ldots, d_n-1$.

Let $G$ be a finite group of order $n$ generated by $a$ and $b$. Prove or disprove: there is a sequence \[ g_1, g_2, g_3, \cdots, g_{2n} \] such that: $(1)$ every element of $G$ occurs exactly twice, and $(2)$ $g_{i+1}$ equals $g_{i}a$ or $g_ib$ for $ i = 1, 2, \cdots, 2n $. (interpret $g_{2n+1}$ as $g_1$.)

Let $n\geq 2$ be an integer. Let us call [i]interval[/i] a subset $A \subseteq \{1,2,\ldots,n\}$ for which integers $1\leq a < b\leq n$ do exist, such that $A = \{a,a+1,\ldots,b-1,b\}$. Let a family $\mathcal{A}$ of subsets $A_i \subseteq \{1,2,\ldots,n\}$, with $1\leq i \leq N$, be such that for any $1\leq i < j \leq N$ we have $A_i \cap A_j$ being an interval. Prove that $\displaystyle N \leq \left \lfloor n^2/4 \right \rfloor$, and that this bound is sharp. (Dan Schwarz - after an idea by Ron Graham)

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i]. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. [i]Author: Vasily Astakhov, Russia[/i]

At the meeting, each person is familiar with 22 people. If two persons $A$ and $B$ know each with one another, among the remaining people they do not have a common friend. For each pair individuals $A$ and $B$ are not familiar with each other, there are among the remaining six common acquaintances. How many people were at the meeting?

Find all pairs of positive integers $(m, n)$, such that in a $m \times n$ table (with $m+1$ horizontal lines and $n+1$ vertical lines), a diagonal can be drawn in some unit squares (some unit squares may have no diagonals drawn, but two diagonals cannot be both drawn in a unit square), so that the obtained graph has an Eulerian cycle.

In a company of 7 sousliks each souslik has 4 friends. Is it always possible to find in this company two non-intersecting groups of 3 sousliks each such that in both groups all sousliks are friends?

One country has $n$ cities and every two of them are linked by a railroad. A railway worker should travel by train exactly once through the entire railroad system (reaching each city exactly once). If it is impossible for worker to travel by train between two cities, he can travel by plane. What is the minimal number of flights that the worker will have to use?

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.