[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).

In a city's bus route system, any two routes share exactly one stop, and every route includes at least four stops. Prove that the stops can be classified into two groups such that each route includes stops from each group.

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.

Let $G$ be a graph on $n\geq 6$ vertices and every vertex is of degree at least 3. If $C_{1}, C_{2}, \dots, C_{k}$ are all the cycles in $G$, determine all possible values of $\gcd(|C_{1}|, |C_{2}|, \dots, |C_{k}|)$ where $|C|$ denotes the number of vertices in the cycle $C$.

$1)$. Prove a graph with $2n$ vertices and $n+2$ edges has an independent set of size $n$ (there are $n$ vertices such that no two of them are adjacent ). $2)$.Find the number of graphs with $2n$ vertices and $n+3$ edges , such that among any $n$ vertices there is an edge connecting two of them

Let $T$ be a tree with$ n$ vertices. Choose a positive integer $k$ where $1 \le k \le n$ such that $S_k$ is a subset with $k$ elements from the vertices in $T$. For all $S \in S_k$, define $c(S)$ to be the number of component of graph from $S$ if we erase all vertices and edges in $T$, except all vertices and edges in $S$. Determine $\sum_{S\in S_k} c(S)$, expressed in terms of $n$ and $k$.

A social club has $2k+1$ members, each of whom is fluent in the same $k$ languages. Any pair of members always talk to each other in only one language. Suppose that there were no three members such that they use only one language among them. Let $A$ be the number of three-member subsets such that the three distinct pairs among them use different languages. Find the maximum possible value of $A$.

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The cycle of graph $G(V,E)$ is a set of distinct vertices ${v_1,v_2...,v_n}\subseteq V$, $v_iv_{i+1}\in E$ for all $1\leq i\leq n$ $(n\geq 3, v_{n+1}=v_1)$; a cycle containing a chord is the cycle ${v_1,v_2...,v_n}$, such that there exist $i,j, 1< i-j< n-1$, satisfying $v_iv_j\in E$.

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.

Given seven points in the plane, some of them are connected by segments such that: [b](i)[/b] among any three of the given points, two are connected by a segment; [b](ii)[/b] the number of segments is minimal. How many segments does a figure satisfying [b](i)[/b] and [b](ii)[/b] have? Give an example of such a figure.

Given $S$ be the finite lattice (with integer coordinate) set in the $xy$-plane. $A$ is the subset of $S$ with most elements such that the line connecting any two points in $A$ is not parallel to $x$-axis or $y$-axis. $B$ is the subset of integer with least elements such that for any $(x,y)\in S$, $x \in B$ or $y \in B$ holds. Prove that $|A| \geq |B|$.

Given $5$ points in a plane, no three of them being collinear. Each two of these $5$ points are joined with a segment, and every of these segments is painted either red or blue; assume that there is no triangle whose sides are segments of equal color. [b]a.)[/b] Show that: [i](1)[/i] Among the four segments originating at any of the $5$ points, two are red and two are blue. [i](2)[/i] The red segments form a closed way passing through all $5$ given points. (Similarly for the blue segments.) [b]b.)[/b] Give a plan how to paint the segments either red or blue in order to have the condition (no triangle with equally colored sides) satisfied.

Graph $G$ is defined in 3d space. It has $e$ edges and every vertex are connected if the distance between them is $1.$ Given that there exists the Hamilton cycle, prove that for $e>1,$ we have $$\min d(v)\le 1+2\left(\frac{e}{2}\right)^{0.4}.$$

In a school, there are 2021 students, each having exactly $k$ friends. There aren't three students such that all three are friends with each other. What is the maximum possible value of $k$?

There are infinitely many people registered on the social network Mugbook. Some pairs of (different) users are registered as friends, but each person has only finitely many friends. Every user has at least one friend. (Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.) Each person is required to designate one of their friends as their best friend. If $A$ designates $B$ as her best friend, then (unfortunately) it does not follow that $B$ necessarily designates $A$ as her best friend. Someone designated as a best friend is called a $1$-best friend. More generally, if $n> 1$ is a positive integer, then a user is an $n$-best friend provided that they have been designated the best friend of someone who is an $(n-1)$-best friend. Someone who is a $k$-best friend for every positive integer $k$ is called popular. (a) Prove that every popular person is the best friend of a popular person. (b) Show that if people can have infinitely many friends, then it is possible that a popular person is not the best friend of a popular person. [i]Romania (Dan Schwarz)[/i]

Adam, Benin, Chiang, Deshawn, Esther, and Fiona have internet accounts. Some, but not all, of them are internet friends with each other, and none of them has an internet friend outside this group. Each of them has the same number of internet friends. In how many different ways can this happen? $ \textbf{(A)}\ 60 \qquad\textbf{(B)}\ 170 \qquad\textbf{(C)}\ 290 \qquad\textbf{(D)}\ 320 \qquad\textbf{(E)}\ 660 $

On sport games there was 1991 participant from which every participant knows at least n other participants(friendship is mutual). Determine the lowest possible n for which we can be sure that there are 6 participants between which any two participants know each other.

Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges. [i]David Yang.[/i]

How many coins can be placed on a $10 \times 10$ board (each at the center of its square, at most one per square) so that no four coins form a rectangle with sides parallel to the sides of the board?

An [i]animal[/i] with $n$ [i]cells[/i] is a connected figure consisting of $n$ equal-sized cells[1]. A [i]dinosaur[/i] is an animal with at least $2007$ cells. It is said to be [i]primitive[/i] it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur. (1) Animals are also called [i]polyominoes[/i]. They can be defined inductively. Two cells are [i]adjacent[/i] if they share a complete edge. A single cell is an animal, and given an animal with $n$ cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.

Let $n>1$ be an integer. Given a simple graph $G$ on $n$ vertices $v_1, v_2, \dots, v_n$ we let $k(G)$ be the minimal value of $k$ for which there exist $n$ $k$-dimensional rectangular boxes $R_1, R_2, \dots, R_n$ in a $k$-dimensional coordinate system with edges parallel to the axes, so that for each $1\leq i<j\leq n$, $R_i$ and $R_j$ intersect if and only if there is an edge between $v_i$ and $v_j$ in $G$. Define $M$ to be the maximal value of $k(G)$ over all graphs on $n$ vertices. Calculate $M$ as a function of $n$.

At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid? [i]Proposed by Evan Chen[/i]

In a forest each of $n$ animals ($n\ge 3$) lives in its own cave, and there is exactly one separate path between any two of these caves. Before the election for King of the Forest some of the animals make an election campaign. Each campaign-making animal visits each of the other caves exactly once, uses only the paths for moving from cave to cave, never turns from one path to another between the caves and returns to its own cave in the end of its campaign. It is also known that no path between two caves is used by more than one campaign-making animal. a) Prove that for any prime $n$, the maximum possible number of campaign-making animals is $\frac{n-1}{2}$. b) Find the maximum number of campaign-making animals for $n=9$.

On some planet, there are $2^N$ countries $(N \geq 4).$ Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. [i]Proposed by Tonći Kokan, Croatia[/i]

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