Simple Undirected Graphs: Adjacency matrix and the $(0-1)$ incidence matrix Are there any relation between the adjacency matrix and the $(0-1)$ incidence matrix of a simple undirected graph?
They characterize uniquely the graph, so my intuition says there must be some relation between them.
Which could be these relation? It is only expressed by a formula or it hides something deeper?
 A: If $N$ is the incidence matrix of a simple undirected graph, $A$ the adjacency matrix, and $D$ is the diagonal matrix whose $(i,i)$ entry is the degree of vertex $i$, then one has $$D-A=N^TN.$$ This matrix is known as the Laplacian of the graph.
A: I am not sure what you mean to be the $(0-1)$ incidence matrix. However, for an undirected graph $\mathcal{G} = (V,E)$, where $V$ is the vertex set $\{v_1,\cdots,v_N\}$ with $N$ vertices and $E$ is the set of edges $\{e_1,\cdots,e_M\}$ with $M$ edges, the incidence matrix of an undirected graph is defined as
$$
[D_u]_{ij} =
\begin{cases}
+1, & \{v_i,v_k\} = e_j \text{ for some } k, \\
0, & \text{otherwise}
\end{cases}
$$
and the only connection I am aware of between this and the adjacency matrix $A$ is that
$$
D_u D_u^T = \triangle + A
$$
where $\triangle = \mathrm{diag}(d_1,\cdots,d_N)$ with $d_i$ being the degree of vertex $i$. I am not sure what the properties of $D_u D_u^T$ are.
This is different from the graph Laplacian $L$ as it is defined using the incidence matrix of a directed graph
$$
[D_d]_{ij} =
\begin{cases}
+1, & \text{if } v_i \text{ is the head of } e_j,  \\
-1, & \text{if } v_i \text{ is the tail of } e_j,  \\
0, & \text{otherwise}
\end{cases}
$$
in which
$$
L = \triangle - A = D_d D_d^T.
$$
If you meant to analyze the connection between the adjacency matrix $A$ and the directed incidence matrix $D_d$, there is more you could probably say due to the properties of the Laplacian $L$.
Additional information can be found here, with the definitions for an incidence matrix of a directed and undirected graph being found in Definition 2.2 and Definition 2.4, respectively.
