  We study zero-one laws for random graphs. We focus on the following question
that was asked by many: Given a graph property P, is there a language of graphs
able to express P while obeying the zero-one law? Our results show that on the
one hand there is a (regular) language able to express connectivity and
k-colorability for any constant k and still obey the zero-one law. On the other
hand we show that in any (semiregular) language strong enough to express
Hamiltonicity one can interpret arithmetic and thus the zero-one law fails
miserably. This answers a question of Blass and Harary.
