Before revision:  We introduce formal definitions of complexity for both labelled and unlabelled graphs and prove that the Kolmogorov complexity of a labelled graph is a good approximation of the Kolmogorov complexity of the unlabelled graph and thus a robust definition of graph complexity.
After revision:  We introduce formal definitions of complexity for both labeled and unlabeled graphs and prove that the Kolmogorov complexity of a labelled graph is a good approximation of the Kolmogorov complexity of the unlabelled graph and thus a robust definition of graph complexity.