Show that any graph with $6$ points has a triangle or three points which are not joined to each other.

A complete graph is in a plane such that no three of its vertices are collinear. The edges of the graph, which are straight segments connecting the vertices, are colored with two colors. Prove that there is a non-self-intersecting spanning tree consisting of edges of the same color.

Jerry places at most one rook in each cell of a $2025 \times 2025$ grid of cells. A rook [i]attacks[/i] another rook if the two rooks are in the same row or column and there are no other rooks between them. Determine, with proof, the maximum number of rooks Jerry can place on the grid such that no rook attacks $4$ other rooks.

Let ${A}$ be a finite set and ${\rightarrow}$ be a binary relation on it such that for any ${a,b,c \in A}$, if ${a\neq b}, {a \rightarrow c}$ and ${b \rightarrow c}$ then either ${a \rightarrow b}$ or ${b \rightarrow a}$ (or possibly both). Let ${B,\,B \subset A}$ be minimal with the property: for any ${a \in A \setminus B}$ there exists ${b \in B}$, such that either ${a \rightarrow b}$ or ${b \rightarrow a}$ (or possibly both). Supposing that ${A}$ has at most ${k}$ elements that are pairwise not in relation ${\rightarrow}$, prove that ${B}$ has at most ${k}$ elements.

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.

A graph $G=(V,E)$ is given. If at least $n$ colors are required to paints its vertices so that between any two same colored vertices no edge is connected, then call this graph ''$n-$colored''. Prove that for any $n \in \mathbb{N}$, there is a $n-$colored graph without triangles.

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})$. (a) Let $p$ be a prime. Consider the graph whose vertices are the ordered pairs $(x, y)$ with $x, y \in\{0, 1, . . . , p-1\}$ and whose edges join vertices $(x, y)$ and $(x' , y')$ if and only if $xx'+yy'\equiv 1 \pmod{p}$ . Prove that this graph does not contain $C_{4}$ . (b) Prove that for infinitely many values $n$ there is a graph $G_{n}$ with $e(G_{n}) \geq \frac{n\sqrt{n}}{2}-n$ that does not contain $C_{4}$.

A directed graph (any two distinct vertices joined by at most one directed line) has the following property: If $x, u,$ and $v$ are three distinct vertices such that $x \to u$ and $x \to v$, then $u \to w$ and $v \to w$ for some vertex $w$. Suppose that $x \to u \to y \to\cdots \to z$ is a path of length $n$, that cannot be extended to the right (no arrow goes away from $z$). Prove that every path beginning at $x$ arrives after $n$ steps at $z.$

There are two countries $A$ and $B$, where each countries have $n(\ge 2)$ airports. There are some two-way flights among airports of $A$ and $B$, so that each airport has exactly $3$ flights. There might be multiple flights among two airports; and there are no flights among airports of the same country. A travel agency wants to plan an [i]exotic traveling course[/i] which travels through all $2n$ airports exactly once, and returns to the initial airport. If $N$ denotes the number of all exotic traveling courses, then prove that $\frac{N}{4n}$ is an even integer. (Here, note that two exotic traveling courses are different if their starting place are different.)

Let $n$ be a positive integer. There is a pawn in one of the cells of an $n\times n$ table. The pawn moves from an arbitrary cell of the $k$th column, $k \in \{1,2, \cdots, n \}$, to an arbitrary cell in the $k$th row. Prove that there exists a sequence of $n^{2}$ moves such that the pawn goes through every cell of the table and finishes in the starting cell.

There are $10000$ cities in country, and roads between some cities. Every city has $<100$ roads. Every cycle route with odd number of road consists of $\geq 101 $ roads. Prove that we can divide all cities in $100$ groups with $100$ cities, such that every road leads from one group to other.

For $n$ people, if it is known that (a) there exist two people knowing each other among any three people, and (b) there exist two people not knowing each other among any four people. Find the maximum of $n$. Here, we assume that if $A$ knows $B$, then $B$ knows $A$.

Let $\mathcal{G}$ be a simple graph with $n$ vertices and $m$ edges such that no two cycles share an edge. Prove that $2m < 3n$. [i]Note[/i]: A [i]simple graph[/i] is a graph with at most one edge between any two vertices and no edges from any vertex to itself. A [i]cycle[/i] is a sequence of distinct vertices $v_1, \dots, v_n$ such that there is an edge between any two consecutive vertices, and between $v_n$ and $v_1$. [i]Proposed by Ethan Tan[/i]

Adithya and Bill are playing a game on a connected graph with $n > 2$ vertices, two of which are labeled $A$ and $B$, so that $A$ and $B$ are distinct and non-adjacent and known to both players. Adithya starts on vertex $A$ and Bill starts on $B$. Each turn, both players move simultaneously: Bill moves to an adjacent vertex, while Adithya may either move to an adjacent vertex or stay at his current vertex. Adithya loses if he is on the same vertex as Bill, and wins if he reaches $B$ alone. Adithya cannot see where Bill is, but Bill can see where Adithya is. Given that Adithya has a winning strategy, what is the maximum possible number of edges the graph may have? (Your answer may be in terms of $n$.) [i]Proposed by Steven Liu[/i]

For any natural $n$, $f(n)$ is the number of labeled digraphs with $n$ vertices such that for any vertex the number if in-edges is equal to the number of out-edges and the total of (in+out) edges is even. Let $g(n)$ be the odd-analogous of $f(n)$. Find $g(n)-f(n)$ with proof . [hide=original formulation] Dado $n$ natural, seja $f(n)$ o número de grafos rotulados direcionados com $n$ vértices de modo que em cada vértice o número de arestas que chegam é igual ao número de arestas que saem e o número de arestas total do grafo é par . Defina $g(n)$ analogamente trocando "par" por "ímpar" na definição acima. Calcule $f(n) - g (n)$. (Observação: Um grafo rotulado direcionado é um par $G = (V, E)$ onde $V = \{1, 2, …, n\}$ e $E$ é um subconjunto de $V^2 -\{(i, i); 0 < i < n + 1\}$).[/hide]

Let $n\ge 3$ be an integer. In a country there are $n$ airports and $n$ airlines operating two-way flights. For each airline, there is an odd integer $m\ge 3$, and $m$ distinct airports $c_1, \dots, c_m$, where the flights offered by the airline are exactly those between the following pairs of airports: $c_1$ and $c_2$; $c_2$ and $c_3$; $\dots$ ; $c_{m-1}$ and $c_m$; $c_m$ and $c_1$. Prove that there is a closed route consisting of an odd number of flights where no two flights are operated by the same airline.

Given positive integer $ n \ge 5 $ and a convex polygon $P$, namely $ A_1A_2...A_n $. No diagonals of $P$ are concurrent. Proof that it is possible to choose a point inside every quadrilateral $ A_iA_jA_kA_l (1\le i<j<k<l\le n) $ not on diagonals of $P$, such that the $ \tbinom{n}{4} $ points chosen are distinct, and any segment connecting these points intersect with some diagonal of P.

Let $n \geq 2$ be a positive integer. On a spaceship, there are $n$ crewmates. At most one accusation of being an imposter can occur from one crewmate to another crewmate. Multiple accusations are thrown, with the following properties: • Each crewmate made a different number of accusations. • Each crewmate received a different number of accusations. • A crewmate does not accuse themself. Prove that no two crewmates made accusations at each other.

In a simple graph, there exist two vertices $A,B$ such that there are exactly $100$ shortest paths from $A$ to $B$. Find the minimum number of edges in the graph. [i]CSJL[/i]

Integers not divisible by $2012$ are arranged on the arcs of an oriented graph. We call the [i]weight of a vertex [/i]the difference between the sum of the numbers on the arcs coming into it and the sum of the numbers on the arcs going away from it. It is known that the weight of each vertex is divisible by $2012$. Prove that non-zero integers with absolute values not exceeding $2012$ can be arranged on the arcs of this graph, so that the weight of each vertex is zero. [i]Proposed by W. Tutte[/i]

There are $n$ cities in a country, one of which is the capital. An airline operates bi-directional flights between some pairs of cities such that one can reach any city from any other city. The airline wants to close down some (possibly zero) number of flights, such that the number of flights needed to reach any particular city from the capital does not increase. Suppose that there are an odd number of ways that the airline can do this. Prove that the set of cities can be divided into two groups, such that there is no flight between two cities of the same group. [i]Proposed by Pranjal Srivastava[/i]

Assume that the connected graph $G$ has $n$ vertices all with degree at least three. Prove that there exists a spanning tree of $G$ with more than $\frac{2}{9}n$ leaves.

Let $n$ be a given positive integer. Find the smallest positive integer $k$ for which the following statement is true: for any given simple connected graph $G$ and minimal cuts $V_1, V_2,\ldots, V_n$, at most $k$ vertices can be chosen with the property that picking any two of the chosen vertices there exists an integer $1\le i\le n$ such that $V_i$ separates the two vertices. A partition of the vertices of $G$ into two disjoint non-empty sets is called a [i]minimal cut[/i] if the number of edges crossing the partition is minimal. [i]Proposed by András Imolay, Budapest[/i]

Given $ n$ countries with three representatives each, $ m$ committees $ A(1),A(2), \ldots, A(m)$ are called a cycle if [i](i)[/i] each committee has $ n$ members, one from each country; [i](ii)[/i] no two committees have the same membership; [i](iii)[/i] for $ i \equal{} 1, 2, \ldots,m$, committee $ A(i)$ and committee $ A(i \plus{} 1)$ have no member in common, where $ A(m \plus{} 1)$ denotes $ A(1);$ [i](iv)[/i] if $ 1 < |i \minus{} j| < m \minus{} 1,$ then committees $ A(i)$ and $ A(j)$ have at least one member in common. Is it possible to have a cycle of 1990 committees with 11 countries?

[b](i)[/b] Determine the smallest number of edges which a graph of $ n$ nodes may have given that adding an arbitrary new edge would give rise to a 3-clique (3 nodes joined pairwise by edges). [b](ii)[/b] Determine the smallest number of edges which a graph of $ n$ nodes may have given that adding an arbitrary new edge would give rise to a 4-clique (4 nodes joined pairwise by edges).