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  .
After 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 .