#### Title

#### Document Type

Article

#### Publication Date

2001

#### Abstract

We prove that if 10 ≦ (^{k}_{2}) ≦ *m *< (^{k+1}_{2}) then the number of paths of length three in a graph *G* of size *m* is at most 2*m*(*m – k*)(*k* - 2)/*k*. Equality is attained if *G* is the union of *K _{k}* and isolated vertices. We also give asymptotically best possible bounds for the maximal number of paths of length

*s*, for arbitrary

*s*, in graphs of size

*m*. Lastly, we discuss the more general problem of maximizing the number of subgraphs isomorphic to a given graph

*H*in graphs of size

*m*.

#### Publication Title

Studia Scientiarum Mathematicarum Hungarica

#### Volume

38

#### Issue

1-4

#### First Page

115

#### Last Page

137

#### Required Publisher's Statement

© Akadémiai Kiadó Zrt.

#### Recommended Citation

Bollobás, Béla and Sarkar, Amites, "Paths in Graphs" (2001). *Mathematics.* Paper 81.

http://cedar.wwu.edu/math_facpubs/81

## Comments

This is the authors' refereed version of the article.