Extremal graph theory

Builds on Graph Subgraph Graph isomorphism

Definition

Let $H$ be a finite simple graph with at least one edge, and let $n \ge 1$ be an integer. A graph $G$ is $H$ -free if no subgraph of $G$ is isomorphic to $H$ . The extremal number $\mathrm{ex}(n, H)$ is the largest number of edges of an $H$ -free graph with $n$ vertices. An $H$ -free graph with $n$ vertices and $\mathrm{ex}(n, H)$ edges is an extremal graph for $H$ . Extremal graph theory is the study of $\mathrm{ex}(n, H)$ , of the extremal graphs, and of similar maximum and minimum problems for graphs.

Remarks

Example: $\mathrm{ex}(4, K_3) = 4$ . The $4$ -cycle has $4$ edges and no triangle. A graph on $4$ vertices with $5$ edges is $K_4$ minus one edge, and it contains a triangle.

Non-example: $K_4$ is not counted for $\mathrm{ex}(4, K_3)$ , because it is not $K_3$ -free.

The maximum exists, since the empty graph on $n$ vertices is $H$ -free and the number of edges is at most $\binom{n}{2}$ . For complete graphs, Turán's theorem says that $\mathrm{ex}(n, K_{r+1})$ is the number of edges of the Turán graph $T(n, r)$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Graph concept
Graph isomorphism concept
Subgraph concept
Extremal graph theory definition

Where this leads

2 pages build on this one.

Tag	`DRGS5TT784`
URI	`m2://DRGS5TT784`
Kind	definition
Writing	W0 stub
MSC	05C35
Defines	Extremal graph theory
Uses	Graph, Subgraph, Graph isomorphism
Changed	2 November 2026

Extremal graph theory

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by