What does the multiplication of incidence matrices mean in terms of graph theory? Let $A$ be the incidence matrix (not adjacency matrix!) of an undirected graph $G=(V,E)$.  What does the matrix product $AA^T$ represent in terms of graphs? What about $A^TA$?

Suppose $G$ is a graph with $n$ vertices.
If instead you make A the "signed incidence matrix" (arbitrarily orient the edges of $G$ and put 1 as the $ij^{th}$ entry if there is an edge from $v_i$ to $v_j$. Put $-1$ as the $ij^{th}$ entry if there is an edge from $v_j$ to $v_i$.), then the matrix $L=AA^t$ is called the "Laplacian" of $G$. The laplacian has cool properties. 
For instance, rank($L)=n- \# \{\textrm{connected components of } G\}$.
If $G$ is connected, then $det(\tilde{L}) = \#\{\textrm{ spanning trees of } G\}$. Where $\tilde{L}$ is a matrix obtained from $L$ by deleting the $i^{th}$ row and $j^{th}$ column of $L$ for any $i,j$!
