Every graph \(G\)  can be naturally encoded using the string representation of an upper triangle of its adjacency matrix. Kolmogorov complexity of a graph could be defined as a Kolmogorov complexity of that string [1]}, [2]}. It gives estimations \(K(G) = O(n^2)\) , \(K(G|n) = O(n^2)\) . Alternatively, \(n\) -vertex connected labeled graph can be represented as a list of edges with ends of each edge encoded using their binary representations concatenated with a binary representation of \(n\) . It gives estimations \(K(G) \le 2m\log (n) + \log (n) = O(m\log (n))\) , \(K(G|n) \le 2m\log (n) = O(m\log (n))\)  [3]}, [1]}.
