A connected graph is given. Prove that its vertices can be coloured blue and green and some of its edges marked so that every two vertices are connected by a path of marked edges, every marked edge connects two vertices of different colour and no two green vertices are connected by an edge of the original graph.

Let $T$ be a tree with $n$ vertices; that is, a connected simple graph on $n$ vertices that contains no cycle. For every pair $u$, $v$ of vertices, let $d(u,v)$ denote the distance between $u$ and $v$, that is, the number of edges in the shortest path in $T$ that connects $u$ with $v$. Consider the sums \[W(T)=\sum_{\substack{\{u,v\}\subseteq V(T)\\ u\neq v}}d(u,v) \quad \text{and} \quad H(T)=\sum_{\substack{\{u,v\}\subseteq V(T)\\ u\neq v}}\frac{1}{d(u,v)}\] Prove that \[W(T)\cdot H(T)\geq \frac{(n-1)^3(n+2)}{4}.\]

There are $N$ cities in a country. Any two of them are connected either by a road or by an airway. A tourist wants to visit every city exactly once and return to the city at which he started the trip. Prove that he can choose a starting city and make a path, changing means of transportation at most once.

Is it true that in any $2$-connected graph with a countably infinite number of vertices it's always possible to find a trail that is infinite in one direction? [i]Submitted by Balázs Bursics and Anett Kocsis, Budapest[/i]

Let $n$ be a positive integer. Find the smallest positive integer $k$ with the property that for any colouring nof the squares of a $2n$ by $k$ chessboard with $n$ colours, there are $2$ columns and $2$ rows such that the $4$ squares in their intersections have the same colour.

Given two integers $h \geq 1$ and $p \geq 2$, determine the minimum number of pairs of opponents an $hp$-member parliament may have, if in every partition of the parliament into $h$ houses of $p$ member each, some house contains at least one pair of opponents.

Let $n\geqslant 2$ be a positive integer. Paul has a $1\times n^2$ rectangular strip consisting of $n^2$ unit squares, where the $i^{\text{th}}$ square is labelled with $i$ for all $1\leqslant i\leqslant n^2$. He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then [i]translate[/i] (without rotating or flipping) the pieces to obtain an $n\times n$ square satisfying the following property: if the unit square in the $i^{\text{th}}$ row and $j^{\text{th}}$ column is labelled with $a_{ij}$, then $a_{ij}-(i+j-1)$ is divisible by $n$. Determine the smallest number of pieces Paul needs to make in order to accomplish this.

The $2001$ towns in a country are connected by some roads, at least one road from each town, so that no town is connected by a road to every other city. We call a set $D$ of towns [i]dominant[/i] if every town not in $D$ is connected by a road to a town in $D$. Suppose that each dominant set consists of at least $k$ towns. Prove that the country can be partitioned into $2001-k$ republics in such a way that no two towns in the same republic are connected by a road.

It is known that each two of the 12 competitors, that participated in the finals of the competition “Mathematical duels”, have a common friend among the other 10. Prove that there is one of them that has at least 5 friends among the group.

Given a positive integer number $n$, determine the maximum number of edges a triangle-free Hamiltonian simple graph on $n$ vertices may have.

Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called [i]simple[/i] if it satisfies $(x \times y) \times z = x \times (y \times z)$ for all $x,y,z \in S$ and $x \times y \in \{x,y\}$ for all $x,y \in S$. Given a simple operation $\times$ on $S$, any string of elements in $S$ can be reduced to a single element, such as $xyz \to x \times (y \times z)$. A string of variables in $S$ is called[i] full [/i]if it contains each variable in $S$ at least once, and two strings are [i]equivalent[/i] if they evaluate to the same variable regardless of which simple $\times$ is chosen. For example $xxx$, $xx$, and $x$ are equivalent, but these are only full if $n=1$. Suppose $T$ is a set of strings such that any full string is equivalent to exactly one element of $T$. Determine the number of elements of $T$.

In the country there're $N$ cities and some pairs of cities are connected by two-way airlines (each pair with no more than one). Every airline belongs to one of $k$ companies. It turns out that it's possible to get to any city from any other, but it fails when we delete all airlines belonging to any one of the companies. What is the maximum possible number of airlines in the country ?

In a group of people, there are some mutually friendly pairs. For positive integer $k\ge3$ we say the group is $k$-great, if every (unordered) $k$-tuple of people from the group can be seated around a round table it the way that all pairs of neighbors are mutually friendly. [i](Since this was the 67th year of CZE/SVK MO,)[/i] show that if the group is 6-great, then it is 7-great as well. [b]Bonus[/b] (not included in the competition): Determine all positive integers $k\ge3$ for which, if the group is $k$-great, then it is $(k+1)$-great as well.

There were finitely many persons at a party among whom some were friends. Among any $4$ of them there were either $3$ who were all friends among each other or $3$ who weren't friend with each other. Prove that you can separate all the people at the party in two groups in such a way that in the first group everyone is friends with each other and that all the people in the second group are not friends to anyone else in second group. (Friendship is a mutual relation).

Every two residents of a city have an even number of common friends in the city. One day, some of the people sent postcards to some of their friends. Each resident with odd number of friends sent exactly one postcard, and every other - no more than one. Every resident received no more than one postcard. Prove that the number of ways the cards could be sent is odd.

In an election, there are $1395$ candidates and some voters. Each voter, arranges all the candidates by the priority order. We form a directed graph with $1395$ vertices, an arrow is directed from $U$ to $V$ when the candidate $U$ is at a higher level of priority than $V$ in more than half of the votes. (otherwise, there's no edge between $U,V$) Is it possible to generate all complete directed graphs with $1395$ vertices?

Determine the largest positive integer $n$ for which there exist pairwise different sets $\mathbb{S}_1 , ..., \mathbb{S}_n$ with the following properties: $1$) $|\mathbb{S}_i \cup \mathbb{S}_j | \leq 2004$ for any two indices $1 \leq i, j\leq n$, and $2$) $\mathbb{S}_i \cup \mathbb{S}_j \cup \mathbb{S}_k = \{ 1,2,...,2008 \}$ for any $1 \leq i < j < k \leq n$ [i]Proposed by Ivan Matic[/i]

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 an arbitrarily chosen finite simple graph. We write non-negative integers on the vertices of the graph such that for each vertex $v$ in $G,$ the number written on $v$ is equal to the number of vertices adjacent to $v$ where an even number is written. Prove that the number of ways to achieve this is a power of $2$.

In the simple and connected graph $G$ let $x_i$ be the number of vertices with degree $i$. Let $d>3$ be the biggest degree in the graph $G$. Prove that if : $$x_d \ge x_{d-1} + 2x_{d-2}+... +(d-1)x_1$$ Then there exists a vertex with degree $d$ such that after removing that vertex the graph $G$ is still connected. Proposed by [i]Ali Mirzaie[/i]

Smallville is populated by unmarried men and women, some of which are acquainted. The two City Matchmakers know who is acquainted with whom. One day, one of the matchmakers claimed: "I can arrange it so that every red haired man will marry a woman with who he is acquainted." The other matchmaker claimed: "I can arrange it so that every blonde woman will marry a man with whom she is acquainted." An amateur mathematician overheard this conversation and said: "Then it can be arranged so that every red haired man will marry a woman with whom he is acquainted and at the same time very blonde woman will marry a man with who she is acquainted." Is the mathematician right?

A school organizes optional lectures for 200 students. At least 10 students have signed up for each proposed lecture, and for any two students there is at most one lecture that both of them have signed up for. Prove that it is possible to hold all these lectures over 211 days so that no one has to attend two lectures in one day.

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

Let $n$ be an odd positive integer. There is a graph $G$ with $2n$ vertices such that if you partition the vertices into two groups $A$ and $B$ with $n$ vertices each, then the subgraph consisting of only vertices and edges within $A$ is connected and has a closed path containing all of its edges, starting and ending with the same vertex. The same condition is true for $B$ as well. Is $G$ necessarily a clique? [i](Proposed by Ho Janson)[/i]

In a given group of people $\mathcal{F}$, each member has at least two acquaintances from $\mathcal{F}$. Moreover, for each cycle $A_{1} \leftrightarrow A_{2} \leftrightarrow ... \leftrightarrow A_{n} \leftrightarrow A_{1}$ in $\mathcal{F}$ (here '$X \leftrightarrow Y$' means that $X$ and $Y$ are acquaintances), each $A_i$ knows exactly two other members $A_j$ of the cycle. Prove that there exist $X, Y \in \mathcal{F}$ such that each of them has exactly two acquaintances in $\mathcal{F}$, and $X, Y$ have at least one common acquaintance in the group. [i]Authored by Mirko Petrusevski[/i]