In fact, it is true.

First observe that $L(G)D(G)L(G)=-2L(G)$ immediately follows from $L(G)D(G) + 2I = (\vec{2}-\vec{d})\vec{1}^\top$, where vector $\vec{d}$ is the vertex degree sequence of $G$.

Imagine $G$ is not a tree. Then $G$ is disconnected, and $L(G)$ has an eigenvector $\vec{u}$ for the zero eigenvalue, such that $\vec{u}^\topL(G)=0$ and $\vec{1}^\top u =0$.

Multiplying $L(G)D(G) + 2I = (\vec{2}-\vec{d})\vec{1}^\top by $\vec{u}^\top$ from the left we obtain $2\vec{u}^\top + \vec{u}^\top\vec{d}\vec{1}^\top = 0$, which means that $u_i=u_j$, which is impossible since $\vec{1}^\top u =0$. Hence, $G$ is a tree.

Mikhail V. Goubko

Are you sure that

( Imagine $G$ is not a tree. Then $G$ is disconnected.. )

is it a true statement?

Counterexample: A complete graph is connected but not a tree.

Regards

"Are you sure that

( Imagine $G$ is not a tree. Then $G$ is disconnected.. )

is it a true statement?

Counterexample: A complete graph is connected but not a tree."

In the problem statement above we have "...some graph G (probably, disconnected) with n vertices and n-1 edges...". Therefore, the counterexample above is not relevant.

However, it is a good question, whether we can get rid of the assumption that G has n-1 edges.

It is easy to see that from $L(G)D(G) + 2I = (\vec{2}-\vec{d})\vec{1}^\top$ it follows that G has $n$ vertices and $n-1$ edges (and hence, is a tree or a disconnected graph).

Let us multiply both sides by $\vec{1}^\top$ from the left and by $\vec{1}$ from the right. Since $L(G)$ is a Laplacian matrix of a graph, we have $1^\top L(G)=0$, and, hence, $2n = (2n-\vec{1}^\top\vec{d})n$. Regrouping, we obtain \sum_{i=1}^n d_i = 2(n-1). By Euler theorem, G has n-1 edges.