Problem 928

Solution:
First, we find the probability that all vertices have even degree. Arbitrarily number the vertices $1, 2, 3, 4, 5, 6$. Flip the coin for all the edges out of vertex $1$; this vertex ends up with even degree with probability $\frac{1}{2}$. Next we flip for all the remaining edges out of vertex $2$; regardless of previous edges, vertex $2$ ends up with even degree with probability $\frac{1}{2}$, and so on through vertex $5$. Finally, if vertices $1$ through $5$ all have even degree, vertex $6$ must also have even degree. So all vertices have even degree with probability $\frac{1}{2^5} = \frac{1}{32}$.

There are $\binom{6}{2} = 15$ edges total, so there are $2^{15}$ total possible graphs, of which $2^{10}$ have all vertices with even degree. Observe that exactly $10$ of these latter graphs are not good, namely, the $\frac{1}{2} \binom{6}{3}$ graphs composed of two separate triangles. So $2^{10} - 10$ of our graphs are good, and the probability that a graph is good is $\frac{2^{10} - 10}{2^{15}}$.