Given is a simple connected graph with $2n$ vertices. Prove that its vertices can be colored with two colors so that if there are $k$ edges connecting vertices with different colors and $m$ edges connecting vertices with the same color, then $k-m \geq n$.

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.

In a $m\times n$ square grid, with top-left corner is $A$, there is route along the edges of the grid starting from $A$ and visits all lattice points (called "nodes") exactly once and ending also at $A$. a. Prove that this route exists if and only if at least one of $m,\ n$ is odd. b. If such a route exists, then what is the least possible of turning points? *A turning point is a node that is different from $A$ and if two edges on the route intersect at the node are perpendicular.

There are $N$ points on the plane; no three of them belong to the same straight line. Every pair of points is connected by a segment. Some of these segments are colored in red and the rest of them in blue. The red segments form a closed broken line without self-intersections(each red segment having only common endpoints with its two neighbors and no other common points with the other segments), and so do the blue segments. Find all possible values of $N$ for which such a disposition of $N$ points and such a choice of red and blue segments are possible.

Let $(v_1, ..., v_{2^n})$ be the vertices of an $n$-dimensional hypercube. Label each vertex $v_i$ with a real number $x_i$. Label each edge of the hypercube with the product of labels of the two vertices it connects. Let $S$ be the sum of the labels of all the edges. Over all possible labelings, find the minimum possible value of $\frac{S}{x^2_1+ x^2_2+ ...+ x^2_n}$ in terms of $ n$. Note: an $n$ dimensional hypercube is a graph on $2^n$ vertices labeled labeled with the binary strings of length $n$, where two vertices have an edge between them if and only if their labels differ in exactly one place. For instance, the vertices $100$ and $101$ on the $3$ dimensional hypercube are connected, but the vertices $100$ and $111$ are not.

Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings.

There are $2006$ students and $14$ teachers in a school. Each student knows at least one teacher (knowing is a symmetric relation). Suppose that, for each pair of a student and a teacher who know each other, the ratio of the number of the students whom the teacher knows to that of the teachers whom the student knows is at least $t.$ Find the maximum possible value of $t.$

An $m \times n$ chessboard with $m,n \ge 2$ is given. Some dominoes are placed on the chessboard so that the following conditions are satisfied: (i) Each domino occupies two adjacent squares of the chessboard, (ii) It is not possible to put another domino onto the chessboard without overlapping, (iii) It is not possible to slide a domino horizontally or vertically without overlapping. Prove that the number of squares that are not covered by a domino is less than $\frac15 mn$.

Let $m$ and $n$ be positive integers. For a connected simple graph $G$ on $n$ vertices and $m$ edges, we consider the number $N(G)$ of orientations of (all of) its edges so that, in the resulting directed graph, every vertex has even outdegree. Show that $N(G)$ only depends on $m$ and $n$, and determine its value.

There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n.$ Each pebble is coloured in one of $n$ colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied: [list] [*]The total weights of both piles are the same. [*] Each pile contains two pebbles of each colour. [/list] [i]Proposed by Milan Haiman, Hungary and Carl Schildkraut, USA[/i]

There are $2000$ cities in the country, each of which has exactly three roads to other cities. Prove that you can close $1000$ roads, so that there is not a single closed route in the country, consisting of an odd number of roads.

Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$. If $e(G_{n}) \geq\frac{n\sqrt{n}}{2}+\frac{n}{4}$ ,prove that $G_{n}$ contains $C_{4}$ .

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}.\]

The city of Neverreturn has $N$ bus stops numbered $1, 2, \cdots , N.$ Each bus route is one-way and has only two stops, the beginning and the end. The route network is such that departing from any stop one cannot return to it using city buses. When the mayor notices a route going from a stop with a greater number to a stop with a lesser number, he orders to exchange the number plates of its beginning and its end. Can the plate changing go on infinitely? [i](K. Ivanov )[/i]

Let $A$ be a symmetric $m\times m$ matrix over the two-element field all of whose diagonal entries are zero. Prove that for every positive integer $n$ each column of the matrix $A^n$ has a zero entry.

For 31 years, n (>6) tennis players have records of wins. It turns out that for every two players, there is a third player who has won over them before. Prove that for every integer $k,l$ such that $2^{2^k+1}-1>n, 1<l<2k+1$, there exist $l$ players ($A_1, A_2, ... , A_l$) such that every player $A_{i+1}$ won over $A_i$. ($A_{l+1}$ is same as $A_1$)

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.

We are given a finite, simple, non-directed graph. Ann writes positive real numbers on each edge of the graph such that for all vertices the following is true: the sum of the numbers written on the edges incident to a given vertex is less than one. Bob wants to write non-negative real numbers on the vertices in the following way: if the number written at vertex $v$ is $v_0$, and Ann's numbers on the edges incident to $v$ are $e_1,e_2,\ldots,e_k$, and the numbers on the other endpoints of these edges are $v_1,v_2,\ldots,v_k$, then $v_0=\sum_{i=1}^k e_iv_i+2022$. Prove that Bob can always number the vertices in this way regardless of the graph and the numbers chosen by Ann. Proposed by [i]Boldizsár Varga[/i], Verőce

Consider $9$ points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $\,n\,$ such that whenever exactly $\,n\,$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

A school has 2021 students, each of which knows at least 45 of the other students (where "knowing" is mutual). Show that there are four students who can be seated at a round table such that each of them knows both of her neighbours.

In a school class with $ 3n$ children, any two children make a common present to exactly one other child. Prove that for all odd $ n$ it is possible that the following holds: For any three children $ A$, $ B$ and $ C$ in the class, if $ A$ and $ B$ make a present to $ C$ then $ A$ and $ C$ make a present to $ B$.

Let $G$ be the complete graph on $2015$ vertices. Each edge of $G$ is dyed red, blue or white. For a subset $V$ of vertices of $G$, and a pair of vertices $(u,v)$, define \[ L(u,v) = \{ u,v \} \cup \{ w | w \in V \ni \triangle{uvw} \text{ has exactly 2 red sides} \}\]Prove that, for any choice of $V$, there exist at least $120$ distinct values of $L(u,v)$.

We have a bipartite graph $G$ (with parts $X$ and $Y$). We orient each edge arbitrarily. [i]Hessam[/i] chooses a vertex at each turn and reverse the orientation of all edges that $v$ is one of their endpoint. Prove that with these steps we can reach to a graph that for each vertex $v$ in part $X$, $\deg^{+}(v)\geq \deg^{-}(v)$ and for each vertex in part $Y$, $\deg^{+}v\leq \deg^{-}v$

A group consist of n tourists. Among every 3 of them there are 2 which are not familiar. For every partition of the tourists in 2 buses you can find 2 tourists that are in the same bus and are familiar with each other. Prove that is a tourist familiar to at most $\displaystyle \frac 2{5}n$ tourists.

In space are given $n\ge 2$ points, no four of which are coplanar. Some of these points are connected by segments. Let $K$ be the number of segments $(K>1)$ and $T$ be the number of formed triangles. Prove that $9T^2<2K^3$.