Introduction to Graph Theory · Problem 2.2

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · mantel-theorem-anti-triangle

Problem

Let

G

be a simple graph with

n

vertices and

e

edges. Assume that

e < n(n-2)/4

. Prove that

G

has an anti-triangle (i.e., three distinct vertices that are pairwise non-adjacent).