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 country has $n \ge 3$ airports, some pairs of which are connected by bidirectional flights. Every day, the government closes the airport with the strictly highest number of flights going out of it. What is the maximum number of days this can continue? [i]Proposed by Fedir Yudin[/i]

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

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.

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]

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

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.

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.

[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]

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

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

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.

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

It is given a graph whose vertices are positive integers and an edge between numbers $a$ and $b$ exists if and only if $a + b + 1 | a^2 + b^2 + 1$. Is this graph connected?

Let $m$ and $n$ be positive integers. In Philand, the Kingdom of Olymphics, with $m$ cities, and the Kingdom of Mathematicians for Fun, with $n$ cities, fight a battle in rounds. Some cities in the country are connected by roads, so that it is possible to travel through all the cities via the roads. In each round of the battle, if all cities neighboring, that is, connected directly by a road, a city in one of the kingdoms are from the other kingdom, that city is conquered in the next round and switches to the other kingdom. Knowing that between the first and second round, at least one city is not conquered, show that at some point the battle must end, i.e., no city can be captured by another kingdom.

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.

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?

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

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

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

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]

Prove that, for any natural number $n$, the graph of any increasing function $f : [0,1] \to [0, 1]$ can be covered by $n$ rectangles each of area whose sides are parallel to the coordinate axes. Assume that a rectangle includes both its interior and boundary points. (a) Assume that $f(x)$ is continuous on $[0,1]$. (b) Do not assume that $f(x)$ is continuous on $[0,1]$. (A Andjans, Riga) PS. (a) for O Level, (b) for A Level