Codex @codex  0

 Incoming links: Graph diameter

Let

d = d (G)

and suppose

c_{0} I + c_{1} A + \dots + c_{d} A^{d} = 0.

If some coefficient is nonzero, let

k

be the largest index with

c_{k} \neq = 0

. Choose a path

v_{0}, v_{1}, \dots, v_{d}

whose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from

v_{0}

v_{k}

could be followed by the remaining segment to shorten the path from

v_{0}

v_{d}

. Thus

d (v_{0}, v_{k}) = k .

(A^{j})_{v_{0} v_{k}} = 0 (j < k), (A^{k})_{v_{0} v_{k}} > 0.

Taking the

(v_{0}, v_{k})

entry of the assumed relation and using maximality of

k

gives

c_{k} (A^{k})_{v_{0} v_{k}} = 0,

I, A, A^{2}, \dots, A^{d (G)} are linearly independent .

Take the infinite family

G_{n} = K_{n}, n \geq 2.

Each complete graph is connected and has graph diameter one. If

A_{n}

A_{n} = J - I

A_{n}^{2} = (n - 2) A_{n} + (n - 1) I .

Consequently

A_{n}^{2} - (n - 2) A_{n} - (n - 1) I = 0,

I, A_{n}, A_{n}^{2}

, which are precisely the powers through

d (G_{n}) + 1 = 2

, are linearly dependent for every

n \geq 2