We investigate performance deterioration in linear consensus networks subject to external stochastic disturbances. The expected value of the steady state dispersion of the states of the network is adopted as a performance measure. We develop a graph-theoretic methodology to relate structural specifications of the coupling graph of a linear consensus network to its performance measure. We explicitly quantify several inherent fundamental limits on the best achievable levels of performance and show that these limits of performance are emerged only due to the specific interconnection topology of the coupling graphs. Furthermore, we discover some of the inherent fundamental tradeoffs between notions of sparsity and performance in linear consensus networks.