Prove: the number of simple undirected graphs with n different nodes, s.t every node has even degree is $2^\binom{n-1}{2}$
My attempt:
I think the problem is equivalent to the number of $(n \times n)$ symetric matrices with $(0,1)$ entries, trace=0 and the sum of every row is even.
Let $F(n)$ be this number. If we have a $(n-2 \times n-2)$ such matrix:
$$\begin{pmatrix} 0 & \dots & \dots & \dots \\ \dots & 0 & \dots &\dots \\ \dots & \dots & 0 & \dots \\ \dots & \dots & \dots & 0 \end{pmatrix} $$
$$\to $$
$$\begin{pmatrix} 0 & \dots & \dots & \dots & & \\ \dots & 0 & \dots &\dots & & \\ \dots & \dots & 0 & \dots & & \\ \dots & \dots & \dots & 0 & & \\ \dots & \dots & \dots & \dots & 0 & 0 \\ \dots & \dots & \dots & \dots & 0 & 0 \\ \end{pmatrix} $$
We have 2 possibilities for the $2n-4$ blank cells: either $(0,0)$ or $(1,1)$ and the right bottom square has to be only with zeros.
Therefore:
$F(n)=2^{n-2}\cdot F(n-2)$ but how do I get to $2^\binom{n-1}{2}?$
Pick some node. For all edges not incident at this node, you can choose independently whether they exist or not. That's $\binom{n-1}2$ binary choices. Then the constraint uniquely determines the existence of the edges incident at the selected node.