Q2 Matemática  (Mathematical Excellence Olympiad 2019)

Considere alguns gráficos $G$ com nós $2019$. Vamos definir a inversão de um vértice $v$ da seguinte forma: para qualquer outro vértice $u$, se houver uma aresta entre $v$ e $u$, ela será excluída, e se não houver, será adicionada. Queremos minimizar o número de arestas no grafo por várias inversões (podemos inverter o mesmo vértice várias vezes). Encontre o menor número $M$ tal que possamos sempre fazer com que o número de arestas no grafo não seja maior que $M$, para qualquer escolha inicial de $G$. Proposto por Arsenii Nikolaev, Anton Trygub (Ucrânia)