Found problems: 79
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)?
A graph $G$ has $n + k$ vertices. Let $A$ be a subset of $n$ vertices of the graph $G$, and $B$ be a subset of other $k$ vertices. Each vertex of $A$ is joined to at least $k - p$ vertices of $B$. Prove that if $np < k$ then there is a vertex in $B$ that can be joined to all vertices of $A$.
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$
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
On a table there are $100$ red and $k$ white buckets for which all of them are initially empty. In each move, a red and a white bucket is selected and an equal amount of water is added to both of them. After some number of moves, there is no empty bucket and for every pair of buckets that are selected together at least once during the moves, the amount of water in these buckets is the same. Find all the possible values of $k$.
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]
A graph has $17$ points and each point has $4$ edges. Show that there are two points which are not joined and which are not both joined to the same point.
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.
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.$
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.
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}.\]
Let $ G $ be a countably infinite, $ d $ -regular, connected, vertex-transitive graph. Show that there is a complete pairing in $ G $.
In the Cartesian plane, let $G_1$ and $G_2$ be the graphs of the quadratic functions $f_1(x) = p_1x^2 + q_1x + r_1$ and $f_2(x) = p_2x^2 + q_2x + r_2$, where $p_1 > 0 > p_2$. The graphs $G_1$ and $G_2$ cross at distinct points $A$ and $B$. The four tangents to $G_1$ and $G_2$ at $A$ and $B$ form a convex quadrilateral which has an inscribed circle. Prove that the graphs $G_1$ and $G_2$ have the same axis of symmetry.
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.
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.
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 are $2024$ cities in a country, every two of which are bidirectionally connected by exactly one of three modes of transportation - rail, air, or road. A tourist has arrived in this country and has the entire transportation scheme. He chooses a travel ticket for one of the modes of transportation and the city from which he starts his trip. He wants to visit as many cities as possible, but using only the ticket for the specified type of transportation. What is the largest $k$ for which the tourist will always be able to visit at least $k$ cities? During the route, he can return to the cities he has already visited.
[i]Proposed by Bogdan Rublov[/i]
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$.
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.)
Given distinct positive integers \( g \) and \( h \), let all integer points on the number line \( OX \) be vertices. Define a directed graph \( G \) as follows: for any integer point \( x \), \( x \rightarrow x + g \), \( x \rightarrow x - h \). For integers \( k, l (k < l) \), let \( G[k, l] \) denote the subgraph of \( G \) with vertices limited to the interval \([k, l]\). Find the largest positive integer \( \alpha \) such that for any integer \( r \), the subgraph \( G[r, r + \alpha - 1] \) of \( G \) is acyclic. Clarify the structure of subgraphs \( G[r, r + \alpha - 1] \) and \( G[r, r + \alpha] \) (i.e., how many connected components and what each component is like).
Let $G$ be a simple graph with $n$ vertices and $m$ edges. Two vertices are called [i]neighbours[/i] if there is an edge between them. It turns out the $G$ does not contain any cycles of length from 3 to $2k$ (inclusive), where $k\geq2$ is a given positive integer.
a) Prove that it is possible to pick a non-empty set $S$ of vertices of $G$ such that every vertex in $S$ has at least $\left\lceil \frac mn \right\rceil$ neighbours that are in $S$. ($\lceil x\rceil$ denotes the smallest integer larger than or equal to $x$.)
b) Suppose a set $S$ as described in (a) is chosen. Let $H$ be the graph consisting of the vertices in $S$ and the edges between those vertices only. Let $v$ be a vertex of $H$. Prove that at least $\left\lceil \left(\frac mn -1\right)^k \right\rceil$ vertices of $H$ can be reached by starting at $v$ and travelling across the edges of $H$ for at most $k$ steps. (Note that $v$ itself satisfies this condition, since it can be reached by starting at $v$ and travelling along the edges of $H$ for 0 steps.)
There are $n$ vertices and $m > n$ edges in a graph. Each edge is colored either red or blue. In each year, we are allowed to choose a vertex and flip the color of all edges incident to it. Prove that there is a way to color the edges (initially) so that they will never all have the same color
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
We call a graph symmetric, if we can put its vertices on the plane such that if the edges are segments, the graph has a reflectional symmetry with respect to a line not passing through its vertices. Find the least value of $K$ such that the edges of every graph with $100$ vertices, can be divided into $K$ symmetric subgraphs.
Bertalan thought about a $4$-digit positive number. Then he draw a simple graph on $4$ vertices and wrote the digits of the number to the vertices of the graph in such a way that every vertex received exactly the degree of the vertex. In how many ways could he think about? In a simple graph every edge connects two different vertices, and between two vertices at most one edge can go.