Show that all eigenvalues of a graph $G$ a are equal to $0 \iff G$ is a null graph

Question

I have an idea that I think may work for the first direction, but not quite sure. Can anyone help? Here is my initial idea:

Assume all eigenvalues of $G$ are $0$.

Then, all eigenvalues $\lambda_1, \lambda_2, \dots \lambda_n$ of the associated nxn adjacency matrix A of G are 0. Thus, for a corresponding eigenvector $x$ to eigenvalue $\lambda$, we have by definition

$Ax = \lambda x$ $\implies \ Ax = 0 \implies A = 0$

Hence, $A$ is the null matrix and thus $G$ contains no edges.

I'm not exactly certain of my logic here as I want $G$ to contain no vertices in order to be a null graph... and I'm not sure what else I can say after this.

The second direction is much simpler since it follows from $G$ being null, hence having a null adjacency matrix and all eigenvalues of a null matrix are $0$.

Any help is much appreciated; thanks in advance!

Answer 1

This statement is in general not true, for a reason you pointed out. Any graph with no edges has the zero matrix as its adjacency matrix, regardless of how many vertices it has. However, we can prove the following statement:

Let $G$ be an undirected graph, and $A$ be its adjacency matrix. If every eigenvalue of $A$ is $0$, then $G$ has no edges.

Try to prove this. Here are two hints if you need them:

The adjacency matrix of an undirected graph is symmetric. Symmetric matrices are always diagonalizable.

Additionally, try to find a counterexample to the above statement if we drop the requirement that $G$ be undirected.