Now it is easy to see that for graphs with the property \(X\)  and with \(n\ge n_{\epsilon }\)  the inequality (REF ) holds. It follows by combining inequalities (REF )-(REF ) using the fact that \(K(G|n)\le K(G)\) . It concludes the proof.

Considerations above and proof of Theorem REF  imply that for every \(\epsilon > 0\)  and \(n\) -vertex graph \(G\)  with sufficiently large \(n\) , \(dim_H(G) \ge \frac{1}{(1+\epsilon )\log (p^*)}\frac{K(G)}{n}\) . Interestingly, similar relations between Kolmogorov complexity and analogues of Hausdorff dimension hold for other objects. In particular, for Cantor space \(\mathcal {C}\)  (the space of all infinite 0-1 sequences) it is proved in [1]} that Kolmogorov complexity and effective (or constructive) Hausdorff dimension \(dim_H(s)\)  of each sequence \(s\)  are related as follows: \(dim_H(s)= \liminf \limits _{n \rightarrow \infty } \frac{K(s_n)}{n}\)  (here \(s_n\)  is the prefix of \(s\)  of length \(n\) ). Similar estimations are known for other variants of Hausdorff dimension [2]}, [3]}.
