On the structure of linear graphs

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 Turân. 1 He proved that a graph with kn vertices and Ck,2n 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), 2 and then list (without proofs) several other theorems and conjectures of this nature.Notations.For the present purposes, a graph is simply a finite set of "vertices " together with an assignment of certain pairs of vertices (possibly none) as being "edges."Two vertices in an edge are said to be joined) the order of a vertex is the number of vertices to which it is joined.The complementary graph G* to a graph G has the same vertices as G, but two vertices are joined in G* if and only if they are not joined in G.A complete graph of order k is a graph having k vertices, every two of which are joined.When k = 3, this configuration is called simply a triangle.If E is any set, \ denotes the cardinal number of E. For any real number x, [x] denotes the greatest integer not greater than x, and [x]* the least integer not less than x.We write h(x) =ln(x), h(x) = ln(ln(x)), and generally l r (x) =ln(Z r _i(a:)).Letters like m, n, p, k, N, r, and so on, usually denote positive integers, and e always denotes a positive number less than 1.