math.CO
Proof of the Erd H o s Simonovits conjecture on walks. Let G n be a graph on n vertices and let w k(G n) denote the number of walks of length k in G n divided by n . Erd H o s and Simonovits conjectured that w k(G n) t geq w t(G n) k when k geq t and both t and k are odd. We prove this conjecture.