sagt aus, daß für r ∈ ℕ und für eine ( feste) Konstante c jeder Graph mit einem Durchschnittsgrad von mindestens \begin{eqnarray}c.r.\sqrt{\mathrm{log}\ r}\end{eqnarray}

den vollständigen Graphen K_r der Ordnung r als Minor (Minor eines Graphen) enthält.

Der Satz von Kostochka-Thomason wurde 1982 von A.V. Kostochka bewiesen, und 1984 gab A. Thomason einen einfachen Beweis, der zu einer besseren Konstante c führte.

Aus einem Resultat von B. Bollobás, P. Catlin und P. Erdős von 1980 über Minoren in Zufallsgraphen folgt, daß die obige Forderung an den Durchschnittsgrad größenordnungsmäßig bestmöglich ist. Bereits 1968 bewies W. Mader ein analoges Ergebnis für Graphen mit einem Durchschnittsgrad von mindestens c′ · r · log r.