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.

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

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

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

A graph contains $p$ vertices numbered from $1$ to $p$, and $q$ edges numbered from $p + 1$ to $p + q$. It turned out that for each edge the sum of the numbers of its ends and of the edge itself equals the same number $s$. It is also known that the numbers of edges starting in all vertices are equal. Prove that \[s = \dfrac{1}{2} (4p+q+3).\]

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]

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.

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

It is known that in a group of $2024$ students each student has at least $1011$ acquaintances among the remaining members of the group. What is more, there exists a student that has at least $1012$ acquaintances in the group. Prove that for every pair of students $X, Y$, there exist students $X_0 = X, X_1, ..., X_{n - 1}, X_n = Y$ in the group such that for every index $i = 0, ..., n - 1$, the students $X_i$ and $X_{i + 1}$ are acquaintances. [i]Proposed by Mirko Petruševski[/i]

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 REAL country has $n$ islands, and there are $n-1$ two-way bridges connecting these islands. Any two islands can be reached through a series of bridges. Arctan, the king of the REAL country, found that it is too difficult to manage $n$ islands, so he wants to bomb some islands and their connecting bridges to divide the country into multiple small areas. Arctan wants the number of connected islands in each group is less than $\delta n$ after bombing these islands, and the island he bomb must be a connected area. Besides, Arctan wants the number of islands to be bombed to be as less as possible. Find all real numbers $\delta$ so that for any positive integer $n$ and the layout of the bridge, the method of bombing the islands is the only one. [i]Proposed by chengbilly[/i]

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.

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

Let $ G$ be a graph with $ 2n$ vertexes and $ 2n(n\minus{}1)$ edges.If we color some edge to red,then vertexes,which are connected by this edge,must be colored to red too. But not necessary that all edges from the red vertex are red. Prove that it is possible to color some vertexes and edges in $ G$,such that all red vertexes has exactly $ n$ red edges.

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.

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

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

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

Points $A$ and $B$ lie on the graph of $y=\log_{2}x$. The midpoint of $\overline{AB}$ is $(6, 2)$. What is the positive difference between the $x$-coordinates of $A$ and $B$? $\textbf{(A)}~2\sqrt{11}\qquad\textbf{(B)}~4\sqrt{3}\qquad\textbf{(C)}~8\qquad\textbf{(D)}~4\sqrt{5}\qquad\textbf{(E)}~9$

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