Too many triangles

We study graphs where each edge adjacent to a vertex of small degree (7 or 9 respectively) belongs to many triangles (4 or 5 respectively) and show that these graphs contain a complete graph ( K 6 or K 7 respectively) as a minor. The second case settles a problem of Nevo (Nevo, 2007). Morevover if each edge of a graph belongs to 6 triangles then the graph contains a K 8 - or K 2 , 2 , 2 , 2 , 2 -minor. We then show applications of these structural properties to stress freeness and coloration of graphs. In particular, motivated by Hadwigerʼs conjecture, we prove that every K 7 -minor free graph is 8-colorable.