MathDB
Inequality with degrees in simple graph implies triangle

Source: VJIMC 2024, Category I, Problem 3

April 14, 2024
inequalitiesgraphdegreecombinatorics

Problem Statement

Let nn be a positive integer and let GG be a simple undirected graph on nn vertices. Let did_i be the degree of its ii-th vertex, i=1,…,ni = 1, \dots , n. Denote Δ=max⁡di\Delta=\max d_i. Prove that if ∑i=1ndi2>nΔ(n−Δ),\sum_{i=1}^n d_i^2>n\Delta(n-\Delta), then GG contains a triangle.
Back to ProblemsView on AoPS