Let $G$ be graph on $n$ vertices, $A$ its adjacency matrix, and $I_{n}$ the $n\times n$ identity matrix. Prove that $G$ is connected iff the matrix $(I_{n} + A)^{n-1}$ has no 0s.
My proof:
If the graph is connected the matrix $(I_{n} + A)^{n-1}$ has no 0s.
The identity matrix takes care of the non-zero values for the diagonal (otherwise the diagonals would be 0 since self-loops are disallowed in simple graphs).
If the graph is connected there must exist a path between any two vertices $u,v \in G$. $A^{n-1}_{i,j}$ represents the number of paths of length $n-1$ between any two vertices. If any $A^{n-1}_{i,j}$ would be 0, that would mean that there would not be any path connecting those vertices. Thus, the graph would be disconnected. But we assumed that it was connected
If the matrix $(I_{n} + A)^{n-1}$ has no 0s then G is connected
If every $(I_{n} + A)^{n-1}$ is non-zero this means that there exists at least one path of length $n – 1$ between any two vertices. If this is the case, the graph must be connected.
Is this correct?
Best Answer
It is not enough to check whether the $i,j$ entry of $A^{n-1}$ is equal to $1$; not every connected graph has a path of length $n-1$ between every two vertices. Also, you're wrong about what it means for every entry of $(I+A)^{n-1}$ to be non-zero.
Hint: use the binomial expansion $$ (I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}k A^k $$