Introduction to Graph Theory · Problem 2.4

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · moon-moser-triangle-inequality

Problem

Let

G

be a simple graph with

n

vertices and

k

edges, where

n > 0

. Prove that

G

has at least

\dfrac{k}{3n}\left(4k - n^2\right)

triangles. [Hint: First argue that for any edge

vw

G

, the total number of triangles that contain

v

and

w

is at least

\deg v + \deg w - n

. Then, use the inequality

n\left(a_1^2 + a_2^2 + \cdots + a_n^2\right) \geq (a_1 + a_2 + \cdots + a_n)^2

, which holds for any

n

real numbers

a_1, a_2, \ldots, a_n

. (This is a particular case of the Cauchy--Schwarz inequality or the Chebyshev inequality or the Jensen inequality -- pick your favorite!)]