How does the binomial expansion helps understanding graph connectedness? I read this post about graph connectedness and adjacency matrix. But I do not understand how the last comment about using the binomial expansion would help. I know this approach is correct, but just do not fully grasp it.  
Would you mind to elaborate a little bit more? I did the binomial expansion and got $\binom{n-1}{0}A^{0}+\binom{n-1}{1}A^{1}+.....+\binom{n-1}{n-1}A^{n-1}$ which is a linear combination of all the As. but I still don't know how this helps. 
 A: What is the matrix $A^k$? It is the matrix that will have entry $i,j$ non-zero (strictly positive) if, and only if, there exists a path of length exactly $k$ between nodes $i$ and $j$.
Now, the graph is connected iff there is a path of length at most $n-1$ between every nodes $i,j$. So using the binomial expansion, $II+A)^{n-1}$ will have entry $i,j$ non-zero iff there exists a path of length $1$, or $2$, or [...], or $n-1$ between nodes $i$ and $j$.
Indeed, $$(I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} A^k$$
so for any $1\leq i,j\leq n$,
$$\begin{align}
\left( (I+A)^{n-1} \right)_{ij} &= \sum_{k=0}^{n-1} \binom{n-1}{k} \left(A^k\right)_{ij}\\
&= \binom{n-1}{0} \left(A^0\right)_{ij}
+ \binom{n-1}{1} \left(A^0\right)_{ij} + \dots + \binom{n-1}{n-1} \left(A^{n-1}\right)_{ij}\\
&= \sum_{k=0}^{n-1} \binom{n-1}{k}\cdot \text{(number of paths between $i$ and $j$ of length exactly $k$)}
\end{align}$$
which is zero if, and only if, there is no path of length at most $n-1$ between $i$ and $j$, which is equivalent to not having any path at all between $i$ and $j$.
Side note: this expansion does not tell you how many such path there are, sadly. That is, there is no (as far as I know, at least) direct correspondence between the entry $\left( (I+A)^{n-1} \right)_{ij}$ (which is an integer) and the number of paths between $i,j\in[n]$ in the graph $G$ (whose adjacency matrix is $A$), because of the binomial coefficients which weigh each summand.
A: As far as I understand $$(I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}k A^k$$
Only shows how to calculate $(I+A)^{n-1}$ and there is no some extra meaning in such expansion.
