Problem

Source: 2022 IFYM, Sozopol, final round

Tags: combinatorics, graph theory



A graph $ G$ with $ n$ vertices is given. Some $ x$ of its edges are colored red so that each triangle has at most one red edge. The maximum number of vertices in $ G$ that induce a bipartite graph equals $ y.$ Prove that $ n\ge 4x/y.$