Here Gn denotes a simple undirected graph with n vertices, Kn denotes the complete graph with n vertices, Kn,m the complete bipartite graph whose components have m and n vertices, and Cn a circuit with n vertices. The number of edges in the graph Gn is denoted e(Gn). If n≥5 and e(Gn)≥n24+2, prove that Gn contains two triangles that share exactly one vertex.
Problem
Source: 12-th Hungary-Israel Mathematical Competition 2001
Tags: graph theory, combinatorics proposed, combinatorics