Problem
COM-B1-M12-P021 Set 6. Triangle
#21
★★★★☆ Level 4 of 5
Prove that a graph on \(9\) vertices in which every degree is at least \(5\) contains a triangle.
Look at the neighbors of one vertex.
Choose a vertex \(v\) and \(5\) of its neighbors. If two neighbors are adjacent, they form a triangle with \(v\). If no two of them are adjacent, then each of these neighbors is adjacent to \(v\) and to at most the three remaining vertices, so its degree is at most \(4\), contradiction.
Extremal graph.