Rank of adjacency matrix vs rank of graph Laplacian

Question

What is the relation between rank of the adjacency matrix of a graph and rank of the corresponding graph Laplacian matrix?

Answer 1

There is no simple relation. The rank of Laplacian of a graph is number of vertices minus number of components. There is no simple formula for the rank of the adjacency matrix. It is generally equal to the number of vertices but for complete bipartite graphs it is two. If $\nu(G)$ is the maximum number of edges in a matching, then the adjacency matrix of a tree $T$ on $n$ vertices has rank $2\nu(T)$ and its Laplacian has rank $n-1$.(For the tree part, see the accepted answer to https://mathoverflow.net/questions/134956/determinants-in-graph-theory.)

Answer 2

The relation between the Laplacian matrix $L$ and the oriented incidence matrix $H$ is

$$ L = H^T H, $$

which is always positive semi-definite since $H$ is not full rank. The number of eigenvalues equal to zero for the Laplacian (you can extract the rank from this information and the number of vertices $n$ of the graph) is equal to the number of connected components in the graph given by $H$.