Problem

Source: 2022 Czech and Slovak Olympiad III A p6

Tags: combinatorics, graph theory



Consider any graph with $50$ vertices and $225$ edges. We say that a triplet of its (mutually distinct) vertices is connected if the three vertices determine at least two edges. Determine the smallest and the largest possible number of connected triples. (Jan Mazak, Josef Tkadlec)