Number of labeled graphs of $n$ odd degree vertices

Question

The number of labelled graphs with all vertices of even degree

This question is about number of labeled graphs of $n$ even vertices. I need hint how to find number of labeled graphs of $n$ odd degree vertices. It is clear that answer is $0$ when $n$ is odd.

Answer 1

Should be the same number as the # of graphs with even degree vertices (so according to the question you linked $2^{\binom{n-1}{2}}$ in case $n$ is even).

This is true because, there is a bijection between the graphs where all vertex degrees are even and the graphs where all vertex degrees are odd: Let $G$ be a graph that has only vertices with even degree, and let $\bar G$ be its complement. Clearly ($n$ is even), a single vertex $v$ has $n-1$ possible neighbors, which is an odd number. Since $\deg_G(v)$ is an even number, $\deg_{\bar G}(v)$ has to be an odd number.

Answer 2

Think the adjacency matrix of a graph.

Let $A$ be $n\times n$ matrice such that $A_{ij}\in \{0,1\}$ , $A_{ii}=0$ and $A^T=A$. Then you can say that there are $2^{n(n-1)\over2}$ such matrices as it is enough to fill lower triangle part of matrices.

But you want that $deg(v_i)$ is odd then it means that sum of every cloumn is odd.

Now, fill every cloumn except the last one in lower triangle part. Then you can see that your condition uniqly determine the last one. (if it is already odd put $0$, if not $1$). Thus, answer is equal to find number of such matrices with $(n-1)x(n-1)$ dimension.

Hence, result is $2^{(n-1)(n-2)\over 2}$ as above argument shows.