Problem

Source: Spain 2022/5 (graph formulation)

Tags: combinatorics



Given is a simple graph $G$ with $2022$ vertices, such that for any subset $S$ of vertices (including the set of all vertices), there is a vertex $v$ with $deg_{S}(v) \leq 100$. Find $\chi(G)$ and the maximal number of edges $G$ can have.