##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 792.05076

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Schelp, R.H.; Simonovits, M.

**Title: ** An extremal result for paths. (In English)

**Source: ** Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences, Ann. N. Y. Acad. Sci. 576, 155-162 (1989).

**Review: ** One of the best known extremal results involving paths is the following one proved more than 25 years ago.

Theorem [*P. Erd\H os* and *T. Gallai*, Acta Math. Acad. Sci. Hung. 10, 337-356 (1959; Zbl 090.39401)]: A graph G_{m} on m vertices with at least [m(k-1)+1]/2 edges contains a path P_{k+1} on k+1 vertices. Furthermore, when m = kt the graph tK_{k} contains the maximal number of edges in an m vertex graph with no P_{k+1} and is the unique such graph.

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.

The problem we address here is of a similar nature. Let m,n and k be fixed positive integers with m > n \geq k. We wish to determine the minimum value l such that each graph on m vertices with l vertices of degree at least n contains a P_{k+1}.

A plausible minimum value for l is suggested by the following graph. Let m = t(n+1)+r, 0 \leq r < n+1, with k < 2n+1. Then the graph consisting of t vertex disjoint copies of H = \overline K_{n+1-\lfloor (k-1)/2 \rfloor}+K_{\lfloor (k-1)/2 \rfloor} contains t \lfloor(k- 1)/2\rfloor vertices of degree n and no P_{k+1}. When k is even and r+\lfloor (k-1)/2 \rfloor \geq n, the number of vertices of degree \geq n in this graph can be increased by 1 to t \lfloor (k-1)/2 \rfloor+1 without forcing the graphs to contain a P_{k+1}. Simply take one of the vertices of degree \lfloor (k-1)/2 \rfloor and make it adjacent to the r vertices in no copy of H. Thus we have the following conjecture:

Let m,n, and k be fixed positive integers with m > n \geq k and set \delta = 2 when k is even and \delta = 1 when k is odd. If G_{m} is a graph on m vertices and at least l = \lfloor (k-1)/2 \rfloor \lfloor m/(n+1) \rfloor+\delta vertices of degree \geq n, then G_{m} contains a P_{k+1}.

Although we do not prove the conjectured result, we do show that the value of l given in the conjecture is ``essentially'' correct. Much attention is given to the special case when n+1 \leq m \leq 2n+1. In this case we show that approximately k/2 vertices of degree \geq n is enough to guarantee that G_{m} contains a P_{k+1}. Unfortunately, even for this interval of values we are not able to prove the exact statement of the conjecture.

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C38 Paths and cycles

**Keywords: ** extremal results; paths; maximal number

**Citations: ** Zbl 090.394

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag