Suppose that $G$ is a simple, undirected graph with $n$ vertices and $m$ edges. Conjecture: The total number of vertex paths of length $l$ is at most $$ n (2 m/n)^{l-1} $$
The heuristic basis for this is that the average degree is $2 m/n$, and this is the total number of ways of choosing paths $l$ vertices in such a graph.
Is this conjecture true? Is there another bound known on the number of such paths?
Suppose the graph is connected. Let $\mu$ be the eigenvalue of the adjacency matrix $A$ with the largest magnitude. This is positive and real by the Perron-Frobenius theorem. The number of (not necessarily simple) paths of length $l$ is asymptotic to a polynomial times $\mu^l$. The Rayleigh quotient characterization of the largest eigenvalue says that
$$\mu = \max_v \frac{v^T A v}{v^T v} \ge \frac{\vec{1}^T A \vec{1}}{\vec{1}^T\vec{1}} = \frac{2 ~\# \textrm{edges}}{n} = \frac{2m}{n}$$
where $\vec{1}$ is the all-$1$ vector. You only get equality when the uniform distribution is a principal eigenvector, which means that all vertices have the same degree. Otherwise, the conjecture fails for sufficiently large path lengths $l$ since the conjectured bound is asymptotically smaller than $\mu^l$.
