Summary: The nullity of a graph $G$, denoted by $\eta(G)$, is the multiplicity of the eigenvalue zero in its spectrum. It is known that $\eta(G)\le n-2$ if $G$ is a simple graph on $n$ vertices and $G$ is not isomorphic to $nK_1$. In this paper, we characterize the extremal graphs attaining the upper bound $n-2$ and the second upper bound $n-3$. The maximum nullity of simple graphs with $n$ vertices and $e$ edges, $M(n,e)$, is also discussed. We obtain an upper bound of $M(n,e)$, and characterize $n$ and $e$ for which the upper bound is achieved.

05C50

graph eigenvalue, nullity, clique, girth, diameter