Earlier today, a badly posed graph theory question was down-voted and removed. However, when shorn of its chrome and properly phrased, the question surprisingly has an exact answer! So I thought it would be worth re-posting for the first poster to see.
Essentially, the question asked how many vertex-labeled graphs are there such that every vertex has odd degree.
The answer was requested for 50 vertices, and turns out to be:
$2^{49 \choose 2} = 2^{1176}$
First, all-odd can only work if the number of vertices is even. In which case we can also count the complementary graphs where all degrees are even. And this will work for any number of vertices. Next, the set of cycles (considered over the field Z_2) generates the set of even graphs as a vector space. A basis for this vector space is found by picking a vertex h as the hub, and considering the C(n-1,2) 3-cycles (h,x,y) for all vertices x&y not equal to h. These are all independent because for each 3-cycle, there is an edge xy to which it is the only contributor. So the vector-space has dimension C(n-1,2) and there are 2^C(n-1,2) even graphs.
Has anyone got a nice elementary proof of this?
Start with $K_n$ over the vertices $\{1,2,\ldots, n\}$. Assign an arbitrary colour $\in\{\text{black},\text{white}\}$ to each edge except those connecting some $k$ and $n$ (so that's $n-1\choose 2$ edges). Now pick the colour of edge $kn$ deterministically to make vertex $k$ incident with an even number of black edges. In the end, $n$ is automatically incident with an even number of black edges.