From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that : [b](i)[/b] each pair of consecutive teams on the list have one member in common and [b](ii)[/b] the chain of teams on the list are in rank order. [i]Alternative formulation.[/i] Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$ , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.

In a group of mathematicians, every mathematician has some friends (the relation of friend is reciprocal). Prove that there exists a mathematician, such that the average of the number of friends of all his friends is no less than the average of the number of friends of all these mathematicians.

Let P be a set of 4n points in the plane such that none of the three points are collinear. Prove that if n is large enough, then the following two statements are equivalent. (i) P can be divided into n four-element subsets such that each subset forms the vertices of a convex quadrilateral. (ii) P can not be split into two sets A and B, each with an odd number of elements, so that each convex quadrilateral whose vertices are in P has an even number of vertices in A and B.

Given a (simple) graph $G$ with $n \geq 2$ vertices $v_1, v_2, \dots, v_n$ and $m \geq 1$ edges, Joël and Robert play the following game with $m$ coins: [list=i] [*]Joël first assigns to each vertex $v_i$ a non-negative integer $w_i$ such that $w_1+\cdots+w_n=m$. [*]Robert then chooses a (possibly empty) subset of edges, and for each edge chosen he places a coin on exactly one of its two endpoints, and then removes that edge from the graph. When he is done, the amount of coins on each vertex $v_i$ should not be greater than $w_i$. [*]Joël then does the same for all the remaining edges. [*]Joël wins if the number of coins on each vertex $v_i$ is equal to $w_i$. [/list] Determine all graphs $G$ for which Joël has a winning strategy.

Seventeen people correspond by mail with one another-each one with all the rest. In their letters only three different topics are discussed. each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

On a connected graph $G$, one may perform the following operations: [list] [*]choose a vertice $v$, and add a vertice $v'$ such that $v'$ is connected to $v$ and all of its neighbours [*] choose a vertice $v$ with odd degree and delete it [/list] Show that for any connected graph $G$, we may perform a finite number of operations such that the resulting graph is a clique. Proposed by [i]idonthaveanaopsaccount[/i]

Let $G$ be a connected graph, with degree of all vertices not less then $m \geq 3$, such that there is no path through all vertices of $G$ being in every vertex exactly once. Find the least possible number of vertices of $G.$

I've come across a challenging graph theory problem. Roughly translated, it goes something like this: There are n lines drawn on a plane; no two lines are parallel to each other, and no three lines meet at a single point. Those lines would partition the plane down into many 'area's. Suppose we select one point from each area. Also, should two areas share a common side, we connect the two points belonging to the respective areas with a line. A graph consisted of points and lines will have been made. Find all possible 'n' that will make a hamiltonian circuit exist for the given graph

Viktor and Natalia play a colouring game with a 3-dimensional cube taking turns alternatingly. Viktor goes first, and on each of his turns, he selects an unpainted edge, and paints it violet. On each of Natalia's turns, she selects an unpainted edge, or at most once during the game a face diagonal, and paints it neon green. If the player on turn cannot make a legal move, then the turn switches to the other player. The game ends when nobody can make any more legal moves. Natalia wins if at the end of the game every vertex of the cube can be reached from every other vertex by traveling only along neon green segments (edges or diagonal), otherwise Viktor wins. Who has a winning strategy? (Prove your answer.) [i]Authored by Viktor Simjanoski[/i]

There's a group of $21$ people such that each person has no more than $7$ friends among the others and any two friends have a different number of total friends. Prove that there are $6$ people, none of which knows the others.

A simple graph is called "divisibility", if it's possible to put distinct numbers on its vertices such that there is an edge between two vertices if and only if number of one of its vertices is divisible by another one. A simple graph is called "permutationary", if it's possible to put numbers $1,2,...,n$ on its vertices and there is a permutation $ \pi $ such that there is an edge between vertices $i,j$ if and only if $i>j$ and $\pi(i)< \pi(j)$ (it's not directed!) Prove that a simple graph is permutationary if and only if its complement and itself are divisibility. [i]Proposed by Morteza Saghafian[/i] .

Given a simple, connected graph with $n$ vertices and $m$ edges. Prove that one can find at least $m$ ways separating the set of vertices into two parts, such that the induced subgraphs on both parts are connected.

Prove that we can color every subset with $n$ element of a set with $3n$ elements with $8$ colors . In such a way that there are no $3$ subsets $A,B,C$ with the same color where : $$|A \cap B| \le 1,|A \cap C| \le 1,|B \cap C| \le 1$$ Proposed by [i]Morteza Saghafian[/i] and [i]Amir Jafari[/i]

We call a pair of distinct numbers $(a, b)$ a [i]binary pair[/i] if $ab+1$ is a power of two. Given a set $S$ of $n$ positive integers, what is the maximum possible numbers of binary pairs in S?

There are $n \geq 3$ islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route. After each year, the ferry company will close a ferry route between some two islands $X$ and $Y$. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected to a ferry route to exactly one of $X$ and $Y$, a new route between this island and the other of $X$ and $Y$ is added. Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.

At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$. [i]Proposed by USA.[/i]

Given positive integers $d \ge 3$, $r>2$ and $l$, with $2d \le l <rd$. Every vertice of the graph $G(V,E)$ is assigned to a positive integer in $\{1,2,\cdots,l\}$, such that for any two consecutive vertices in the graph, the integers they are assigned to, respectively, have difference no less than $d$, and no more than $l-d$. A proper coloring of the graph is a coloring of the vertices, such that any two consecutive vertices are not the same color. It's given that there exist a proper subset $A$ of $V$, such that for $G$'s any proper coloring with $r-1$ colors, and for an arbitrary color $C$, either all numbers in color $C$ appear in $A$, or none of the numbers in color $C$ appear in $A$. Show that $G$ has a proper coloring within $r-1$ colors.

There is an integer $n > 1$. There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies. [i]Proposed by Tejaswi Navilarekallu, India[/i]

Let S be a set of $n\geq 3$ points in space. We color some line segments having two points in $S$ as their endpoints red, let $r$ be the number of edges colored red (color $r$ edges red). We know no two colored segmentes have the same length. Proof there is a path of red edges increasing in size of length at least $\Bigg\lceil\frac{2r}{n}\Bigg\rceil$.

Let $r,g,b$ be non negative integers and $\Gamma$ be a connected graph with $r+g+b+1$ vertices. Its edges are colored in red green and blue. It turned out that $\Gamma $ contains A spanning tree with exactly $r$ red edges. A spanning tree with exactly $g$ green edges. A spanning tree with exactly $b$ blue edges. Prove that $\Gamma$ contains a spanning tree with exactly $r$ red edges, $g$ green edges and $b$ blue edges.

A graph is called $7-chip$ if it obtained by removing at most three edges that have no vertex in common from a complete graph with seven vertices. Consider a complete graph $G$ with $v$ vertices which each edge of its is colored blue or red. Prove that there is either a blue path with $100$ edges or a red $7-chip$.

In the class, there are $ 15$ boys and $ 15$ girls. On March $ 8$, some boys made phone calls to some girls to congratulate them on the holiday ( each boy made no more than one call to each girl). It appears that there is a unique way to split the class in $ 15$ pairs (each consisting of a boy and a girl) such that in every pair the boy has phoned the girl. Find the maximal possible number of calls.

$ 1650$ students are arranged in $ 22$ rows and $ 75$ columns. It is known that in any two columns, the number of pairs of students in the same row and of the same sex is not greater than $ 11$. Prove that the number of boys is not greater than $ 928$.

Consider a pyramid with a regular $n$-gon as its base. We colour all the segments connecting two of the vertices of the pyramid except for the sides of the base either red or blue. Show that if $n=9$ then for each such colouring there are three vertices of the pyramid connecting by three segments of the same colour, and that this is not necessarily the case if $n=8$.

Seven points are given in space, no four of which are on a plane. Each of the segments with the endpoints in these points is painted black or red. Prove that there are two monochromatic triangles (not necessarily both of the same color) with no common edge. Does the statement hold for six points?