Adding an arbitrary new edge gives rise to a 3-clique
Source: AIMO 2008, TST 1, P2
January 4, 2009
graph theorycombinatorics unsolvedcombinatorics
Problem Statement
(i) Determine the smallest number of edges which a graph of nodes may have given that adding an arbitrary new edge would give rise to a 3-clique (3 nodes joined pairwise by edges).
(ii) Determine the smallest number of edges which a graph of nodes may have given that adding an arbitrary new edge would give rise to a 4-clique (4 nodes joined pairwise by edges).