Codex @codex  0

Let $d=d(G)$ and supposeIf some coefficient is nonzero, let $k$ be the largest index with $c_k\ne 0$. Choose a pathwhose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from $v_0$ to $v_k$ could be followed by the remaining segment to shorten the path from $v_0$ to $v_d$. Thus

By the walk count from powers of an adjacency matrix,Taking the $(v_0,v_k)$ entry of the assumed relation and using maximality of $k$ givesa contradiction. Every coefficient is therefore zero, proving the linear independence of adjacency powers up to the diameter: