A graph $G$ with $n$ vertex is called [i]good [/i] if every vertex could be labelled with distinct positive integers which are less than or equal $\lfloor \frac{n^2}{4} \rfloor$ such that there exists a set of nonnegative integers $D$ with the following property: there exists an edge between $2$ vertices if and only if the difference of their labels is in $D$. Show that there exists a positive integer $N$ such that for every $n \ge N$, there exist a not-good graph with $n$ vertices.

In the country of Sikinia there are finitely many cities. From each city, exactly three roads go out and each road goes to another Sikinian city. A tourist starts a trip from city $A$ and drives according to the following rule: he turns left at the first city, then right at the next city, and so on, alternately. Show that he will eventually return to $A.$

The towns in one country are connected with bidirectional airlines, which are paid in at least one of the two directions. In a trip from town A to town B there are exactly 22 routes that are free. Find the least possible number of towns in the country.

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

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

In a country there are two-way non-stopflights between some pairs of cities. Any city can be reached from any other by a sequence of at most $100$ flights. Moreover, any city can be reached from any other by a sequence of an even number of flights. What is the smallest $d$ for which one can always claim that any city can be reached from any other by a sequence of an even number of flights not exceeding $d$?

State consists of $2021$ cities, between some of them there are direct flights. Each pair of cities has not more than one flight, every flight belongs to one of $2021$ companies. Call a group of cities [i]incomplete[/i], if at least one company doesn't have any flights between cities of the group. Find the maximum positive integer $m$, so that one can always find an incomplete group of $m$ cities.

Let $ G $ be a countably infinite, $ d $ -regular, connected, vertex-transitive graph. Show that there is a complete pairing in $ G $.

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.

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

Consider five segments $AB_1, AB_2, AB_3, AB_4, AB_5$. From each point $B_i$ there can exit either $5$ segments or no segments at all, so that the endpoints of any two segments of the resulting graph (system of segments) do not coincide. Can the number of free endpoints of the segments thus constructed be equal to $1001$? (A free endpoint is an endpoint from which no segment begins.)

Determine the (real) domain of a function $$y=\sqrt{1-\frac{x}{4}|x|+\sqrt{1-\frac{x}{2}|x|\,}\,}-\sqrt{1-\frac{x}{4}|x|-\sqrt{1-\frac{x}{2}|x|\,}\,}$$ and draw its graph.

A graph $G$ has $n$ vertices ($n>1$). For each edge $e$ let $c(e)$ be the number of vertices of the largest complete subgraph containing $e$. Prove that the inequality (the summation is over all edges of $G$): \[\sum_{e} \frac{c(e)}{c(e)-1}\le \frac{n^2}{2}.\]

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

Is it possible to draw in the plane the graph presented in the figure so that all the vertices are different points and all the edges are unit segments? (The segments can intersect at points different from vertices.)

The edges of a graph $G$ are coloured in two colours. Such that for each colour all the connected components of this graph formed by edges of this colour contains at most $n>1$ vertices. Prove there exists a proper colouring for the vertices of this graph with $n$ colours.

Consider a complete graph on $4046$ nodes, whose edges are colored in some colors. Let's call this graph $k$-good if we can split all its nodes into $2023$ pairs so that there are exactly $k$ distinct colors among the colors of $2023$ edges that connect the nodes from the same pairs. Is it possible that the graph is $999$-good and $1001$-good but not $1000$-good? [i]Proposed by Anton Trygub[/i]

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.

A graph has $30$ points and each point has $6$ edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.

What is the largest possible number of edges in a graph on $2n$ nodes, if there exists exactly one way to split its nodes into $n$ pairs so that the nodes from each pair are connected by an edge? [i]Proposed by Anton Trygub[/i]

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.

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 $n$ be a positive integer and let $G_n$ be the set of all simple graphs on $n$ vertices. For each vertex $v$ of a graph in $G_n$, let $k(v)$ be the maximal cardinality of an independent set of neighbours of $v$. Determine $max_{G \in G_n} \Sigma_{v\in V (G)}k(v)$ and the graphs in $G_n$ that achieve this value.

For any natural $n$, $f(n)$ is the number of labeled digraphs with $n$ vertices such that for any vertex the number if in-edges is equal to the number of out-edges and the total of (in+out) edges is even. Let $g(n)$ be the odd-analogous of $f(n)$. Find $g(n)-f(n)$ with proof . [hide=original formulation] Dado $n$ natural, seja $f(n)$ o número de grafos rotulados direcionados com $n$ vértices de modo que em cada vértice o número de arestas que chegam é igual ao número de arestas que saem e o número de arestas total do grafo é par . Defina $g(n)$ analogamente trocando "par" por "ímpar" na definição acima. Calcule $f(n) - g (n)$. (Observação: Um grafo rotulado direcionado é um par $G = (V, E)$ onde $V = \{1, 2, …, n\}$ e $E$ é um subconjunto de $V^2 -\{(i, i); 0 < i < n + 1\}$).[/hide]

There are 2000 cities in a country and no roads. Prove that some cities can be connected by a road such that there would be 2 cities with 1 road passing through them, there would be 2 cities with 2 roads passim through them,...,there would be 2 cities with 1000 roads passing through them. [I]Proposed by F. Bakharev[/i]