In my book Graphes et algorithmes it is said that he adjacency matrice allows to display either 1-regular graphs (oriented) or simple graphs (unoriented)
We see furthermore that the quantity of information necessary is $N^2$ ($N=[X]$ the vertex number). Why so?
It is said then that for low density graphs ($M\ll N^2$ and for the oriented graphs, $M\ll \frac12N(N+1)$) there is a serious lack of information, and it would be advantageous to describe solely the non-zero terms of the adjacency matrice.
Because that adjacency matrix has one row per vertex and one column per vertex and entries that could be either $0$ or $1$, thus resulting in $N^2$ "bits"?
If we forbid loops, this just says that the diagonal is $0$, taking us down to $N^2-N$ bits. If we consider edges as undirected, the matirix becomes symmetric, leaving us with $\frac{N(N-1)}2$ bits. That is still quadratic in $N$.
Now assume you are not interested in general graphs, but only in a special class, for example rooted trees. A more concise way to encode such a tree is merely list for each non-root vertex its next neighbour closer to the root. That can easily be done with $\sim N\log N$ bits, which is asymptotically much less than $N^2$.