What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov complexity of a graph? Does it make sense to define something in this line at all? I guess one needs a binary string, first of all. Is there then a way to get a binary string from a graph in some unequivocal way, without having to deal with labeling issues, permutations, etc.? 



Compressing Graphs (Kolmogorov complexity of graphs)
Li and Vitányi in their standard textbook on Kolmogorov complexity (3rd edition, p.456) observe



> 
> Almost all strings have high complexity. Therefore, almost all tournaments and almost all undirected graphs have high complexity.
> 
> 
> 


This is made more precise in Section 6.4. In particular, they show that the number of distinct isomorphism classes of undirected graphs with $n$ vertices asymptotically approaches $2^\binom{n}{2}/n!$, with only a small error.


By [Stirling's approximation](http://en.wikipedia.org/wiki/Stirling%27s_approximation), the Kolmogorov complexity of undirected graphs with $n$ vertices can then be seen to be close to $n(n-1)/2 + c$ bits. For undirected graphs the adjacency matrix is symmetric and has 0's on the diagonal, so one only needs to store the $n(n-1)/2$ bits above the diagonal.


This makes more precise the claim made in another answer, that the adjacency matrix representation is optimal. (Note that *close* in this argument may still be an unbounded function of $n$; see also Lemma 6.4.6 and the comment after it.)


* Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edition, Springer-Verlag, 2008. doi: [10.1007/978-0-387-49820-1](http://dx.doi.org/10.1007/978-0-387-49820-1)


