An Extremal Result for Paths a

There are many other results in the literature that use that a graph with many edges or with high-degree vertices has a long path. Several such results are given in the references [ 1-41. The problem we address here is of a similar nature. Let m, n, and k be fixed positive integers with m > n 2 k. We wish to determine the minimum value 1 such that each graph on m vertices with I vertices of degree at least n contains a Pk+l. A plausible minimum value for 1 is suggested by the following graph. Let m = t(n + 1) + r, 0 5 r < n + 1, with k < 2n + 1. Then the graph consisting of t vertex disjoint copies of H = Kn+l-L(k-,)/2, + KL(k_,) /zJ contains tL(k 11/21 vertices of degree n and no Pk+,. When k is even and r + L(k 1)/21 2 n, the number of vertices of degree 2 n in this graph can be increased by 1 to tL(k l) /2J + 1 without forcing the graphs to contain a Pk+l . Simply take one of the vertices of degree L(k 1)/2J and make it adjacent to the r vertices in no copy of ff. Thus we have the following conjecture. CONJECTURE: Let m, n, and k be fixed positive integers with m > n 2 k and set 6 = 2 when k is even and 6 = 1 when k is odd. If G, is a graph on m vertices and at least I = L(k 1)/21 Lm/(n + 1)1 + 6 vertices of degree 2 n, then G, contains a Pk+l .