On the structure of linear graphs. (English) Zbl 0063.01277

Erdős, Pál; Stone, A. H.

Bull. Am. Math. Soc. 52, 1087-1091 (1946).

Introduction: If the numbers of vertices and edges of a (linear) graph are suitably restricted, it is to be expected that something can be said about the configurations which the graph contains. As far as we know the first result in this direction is due to P. Turán [Mat. Fiz. Lapok 48, 436–452 (1941; Zbl 0026.26903, JFM 67.0732.03)]. He proved that a graph with \(kn\) vertices and \(C_{k,2}n^2+1\) edges always contains a complete graph of order \(k+1\). We shall here prove one such theorem (which arose originally out of a topological problem) [A. H. Stone, Connectedness and coherence. Thesis (Ph.D.) Princeton University. (1941)], and then list (without proofs) several other theorems and conjectures of this nature.

MSC:

05C75

Structural characterization of families of graphs