You are here

A Short Proof of Turan' s Theorem

by William Staton

This article originally appeared in:
American Mathematical Monthly
March, 1999

Subject classification(s): Discrete Mathematics | Graph Theory
Applicable Course(s): 2.7 Finite Math | 3.7 Discrete Math

This note shows that graphs with \(n\) vertices containing no complete graph with \(r \) vertices, have no more than \( (r - 2)n^2/(2r - 2) \) edges , for \( r \geq 2\).


A pdf copy of the article can be viewed by clicking below. Since the copy is a faithful reproduction of the actual journal pages, the article may not begin at the top of the first page.

To open this file please click here.

Average: 4.5 (6 votes)