For a finite graph $G$, let $f(G)$ be the number of triangles and $g(G)$ the number of tetrahedra formed by edges of $G$. Find the least constant $c$ such that \[g(G)^3\le c\cdot f(G)^4\] for every graph $G$. [i]Proposed by Marcin Kuczma, Poland [/i]

In the country some mathematicians know each other and any division of them into two sets contain 2 friends from different sets.It is known that if you put any set of four or more mathematicians at a round table so that any two neighbours know each other , then at the table there are two friends not sitting next to each other.We denote by $c_i $ the number of sets of $i$ pairwise familiar mathematicians(by saying "familiar" it means know each other).Prove that $c_1-c_2+c_3-c_4+...=1$

$m,n$ are given integer numbers such that $m+n$ is an odd number. Edges of a complete bipartie graph $K_{m,n}$ are labeled by ${-1,1}$ such that the sum of all labels is $0$. Prove that there exists a spanning tree such that the sum of the labels of its edges is equal to $0$.

[list=1] [*] Let $G$ be a $(4, 4)$ unoriented graph, 2-regulate, containing a cycle with the length 3. Find the characteristic polynomial $P_G (\lambda)$ , its spectrum $Spec (G)$ and draw the graph $G$. [*] Let $G'$ be another 2-regulate graph, having its characteristic polynomial $P_{G'} (\lambda) = \lambda^4 - 4\lambda^2 + \alpha, \alpha \in \mathbb{R}$. Find the spectrum $Spec(G')$ and draw the graph $G'$. [*] Are the graphs $G$ and $G'$ cospectral or isomorphic? [/list]

A graph $G(V,E)$ is triangle-free, but adding any edges to the graph will form a triangle. It's given that $|V|=2019$, $|E|>2018$, find the minimum of $|E|$ .

We label every edge of a simple graph with the difference of the degrees of its endpoints. If the number of vertices is $N$, what can be the largest value of the sum of the labels on the edges? [i]Proposed by Dániel Lenger and Gábor Szűcs, Budapest[/i]

Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges. [i]David Yang.[/i]

At least $3$ players take part in a tennis tournament. Each participant plays exactly one match against each other participant. After the tournament has ended, we find out that each player has won at least one match. (There are no ties in tennis). Show that in the tournament, there was at least one trio of players $A,B,C$ such that $A$ beat $B$, $B$ beat $C$, and $C$ beat $A$.

Let $n \geq 1$ be an integer, and let $S$ be a set of integer pairs $(a,b)$ with $1 \leq a < b \leq 2^n$. Assume $|S| > n \cdot 2^{n+1}$. Prove that there exists four integers $a < b < c < d$ such that $S$ contains all three pairs $(a,c)$, $(b,d)$ and $(a,d)$.

There are $n$ cities on each side of Hung river, with two-way ferry routes between some pairs of cities across the river. A city is “convenient” if and only if the city has ferry routes to all cities on the other side. The river is “clear” if we can find $n$ different routes so that the end points of all these routes include all $2n$ cities. It is known that Hung river is currently unclear, but if we add any new route, then the river becomes clear. Determine all possible values for the number of convenient cities. [i] Proposed by usjl[/i]

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.) [i]Fedor Petrov, Russia[/i]

Let $ n,k$ be given positive integers satisfying $ k\le 2n \minus{} 1$. On a table tennis tournament $ 2n$ players take part, they play a total of $ k$ rounds match, each round is divided into $ n$ groups, each group two players match. The two players in different rounds can match on many occasions. Find the greatest positive integer $ m \equal{} f(n,k)$ such that no matter how the tournament processes, we always find $ m$ players each of pair of which didn't match each other.

Eight football teams play matches against each other in such a way that no two teams meet twice and no three teams play all of the three possible matches. What is the largest possible number of matches?

In a meeting of $4042$ people, there are $2021$ couples, each consisting of two people. Suppose that $A$ and $B$, in the meeting, are friends when they know each other. For a positive integer $n$, each people chooses an integer from $-n$ to $n$ so that the following conditions hold. (Two or more people may choose the same number). [list] [*] Two or less people chose $0$, and if exactly two people chose $0$, they are coupled. [*] Two people are either coupled or don't know each other if they chose the same number. [*] Two people are either coupled or know each other if they chose two numbers that sum to $0$. [/list] Determine the least possible value of $n$ for which such number selecting is always possible.

Let $G = (V, E)$ be a simple connected graph. Show that there exists a subset of edges $F \subseteq E$ such that every vertex in $H = (V, F)$ has odd degree if and only if $|V |$ is even. Note: A connected graph is a graph such that any two vertices have a sequence of edges connecting one to the other. Note: A simple graph has no loops (edges of the form $(v, v)$) or duplicate edges.

A splitting of a planar polygon is a finite set of triangles whose interiors are pairwise disjoint, and whose union is the polygon in question. Given an integer $n \ge 3$, determine the largest integer $m$ such that no planar $n$-gon splits into less than $m$ triangles.

Each two of $n$ students, who attended an activity, have different ages. It is given that each student shook hands with at least one student, who did not shake hands with anyone younger than the other. Find all possible values of $n$.

There are $10^{2015}$ planets in an Intergalactic empire. Every two planets are connected by a two-way space line served by one of $2015$ travel companies. The Emperor would like to close $k$ of these companies such that it is still possible to reach any planet from any other planet. Find the maximum value of $k$ for which this is always possible. (D. Karpov)

During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of mathematicians, there was some moment when both were asleep simultaneously. Prove that, at some moment, three of them were sleeping simultaneously.

There are $ n\ge 1 $ ordered bulbs controlled by $ n $ ordered switches such that the $ k\text{-th} $ switch controls the $ k\text{-th} $ bulb and also the $ j\text{-th} $ bulb if and only if the $ j\text{-th} $ switch controls the $ k\text{-th} $ bulb, for any $ 1\le k,j\le n. $ If all bulbs are off, show that it can be chosen some switches such that, if pushed simmultaneously, the bulbs turn all on.

Two positive integers $a$ and $b$ are prime-related if $a = pb$ or $b = pa$ for some prime $p$. Find all positive integers $n$, such that $n$ has at least three divisors, and all the divisors can be arranged without repetition in a circle so that any two adjacent divisors are prime-related. Note that $1$ and $n$ are included as divisors.

There are $N$ cities in a country. Any two of them are connected either by a road or by an airway. A tourist wants to visit every city exactly once and return to the city at which he started the trip. Prove that he can choose a starting city and make a path, changing means of transportation at most once.

Let $n \geq 3$ be an integer. Two players play a game on an empty graph with $n + 1$ vertices, consisting of the vertices of a regular n-gon and its center. They alternately select a vertex of the n-gon and draw an edge (that has not been drawn) to an adjacent vertex on the n-gon or to the center of the n-gon. The player who first makes the graph connected wins. Between the player who goes first and the player who goes second, who has a winning strategy? [i]Note: an empty graph is a graph with no edges.[/i]

Define a $ k$-[i]clique[/i] to be a set of $ k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

Let $n \geq 3$ be an integer, and consider a set of $n$ points in three-dimensional space such that: [list=i] [*] every two distinct points are connected by a string which is either red, green, blue, or yellow; [*] for every three distinct points, if the three strings between them are not all of the same colour, then they are of three different colours; [*] not all the strings have the same colour. [/list] Find the maximum possible value of $n$.