# Extremal problem: #paths of length l as function of number of edges

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?

• It fails for stars. Jan 14 '16 at 19:01
• Your paths are simple? Jan 15 '16 at 1:23
• It seems more reasonable if you say "at least" instead of "at most" since the Perron-Frobenius eigenvectors tend to have a higher weight on high degree vertices. Jan 15 '16 at 5:01

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$.