A graph property not satisfying a ``zero-one law'' (Q1121916)

We say that a graph has property \(\Pi\) if for no partition of the vertex set into two is the induced bipartite subgraph eulerian. It is shown that the proposition of labelled graphs on n vertices having property \(\Pi\) equals \(\prod^{k}_{i=1}(1-2^{1-2i})\) where k is the integer part of \(1/2\;n\). It is noted in a addition at proof stage that this somewhat obstruse property occurs also in number theory. The proportion, above, equals the density of integers d, amongst squarefree numbers congruent to 3 (mod 4) and having n prime factors, such that the equation \(x^ 2- dy^ 2=-1\) has an integral solution. This density has been studied by \textit{J. Cremona} and \textit{R. Odoni} [J. Lond. Math. Soc., II. Ser. 39, No.1, 16-28 (1989)], who have also shown that a graph G has \(\Pi\) if and only if it has an odd number of spanning trees.