Problem
COM-B1-M09-P021 Minimum Degree \(5\)
#21
★★★★☆ Level 4 of 5
Prove that a graph on \(9\) vertices in which every vertex has degree at least \(5\) must contain a triangle.
Choose a vertex and look at its neighbors.
Choose a vertex \(v\). It has at least \(5\) neighbors. If two of these neighbors are adjacent, then together with \(v\) they form a triangle. If there are no edges among the neighbors of \(v\), then each such neighbor is adjacent to \(v\) and can be adjacent only to the three vertices that are neither \(v\) nor neighbors of \(v\). Its degree is then at most \(1+3=4\), contradicting minimum degree \(5\). Hence a triangle exists.
Good first extremal graph problem.