Proof of the Erdős-Simonovits conjecture on walks

Abstract

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ős and Simonovits conjectured that $w_k(G^n{)}^t\ge w_t(G^n{)}^k$ when $k\ge t$ and both $t$ and $k$ are odd. We prove this conjecture.

4 pages