if a graph with adjacency matrix $A$ and Laplacian $L$ has $k$ distinct eigenvalues then does this fact naturally help define or prove existence of a polynomial $p$ of degree $k-1$ such that $[p(A)]_{ij} \neq 0, \forall i,j$ ? (and similarly for $L$ with may be a different polynomial but with the same degree)

(prove the above without using the fact that diameter of a graph is bounded by $k$)

2more comments