The number $f(n)$ of graphs on the vertex set $\{1,\dots,n\}$,
allowing loops but not multiple edges, is $2^{{n+1\choose
2}}$, with exponential generating function $F(x)=\sum\_{n\geq 0}
2^{{n+1\choose 2}}\frac{x^n}{n!}$. Consider
$$ \sqrt{F(x)} = 1+x+3\frac{x^2}{2!}+23\frac{x^3}{3!}
 +393\frac{x^4}{4!}+13729\frac{x^5}{5!}+\cdots. $$
It's not hard to see that the coefficients 1,1,3,23,393,13729,$\dots$
are positive integers. This is [A178315](https://oeis.org/A178315) in OEIS. Do they have a
combinatorial interpretation?


More generally, we can replace $2^{{n+1\choose 2}}$ with
$\sum\_G t\_1^{c\_1(G)} t\_2^{c\_2(G)}\cdots$,
where $G$ ranges over the same graphs on $\{1,\dots,n\}$, and where
$c\_i(G)$ is the number of connected components of $G$ with $i$
vertices. Now we will get polynomials in the $t\_i$'s with positive
integer coefficients, the first four being
$$ t\_1 $$
$$ t\_1^2+2t\_2 $$
$$ t\_1^3+6t\_1t\_2+16t\_3 $$
$$ t\_1^4+12t\_1^2t\_2+64t\_1t\_3+12t\_2^2+304t\_4. $$
Again we can ask for a combinatorial interpretation of the
coefficients.


**Note.** What happens if we don't allow loops, so we are looking
at $\sqrt{\sum\_{n\geq 0}2^{{n\choose 2}}\frac{x^n}{n!}}$? Now the
coefficient of $\frac{x^n}{n!}$ is equal to the coefficient of
$\frac{x^n}{n!}$ in $\sqrt{F(x)}$, divided by $2^n$, which in general is not
an integer. Hence it makes more sense combinatorially to allow loops.



The "square root" of a graph?
There is a fixed-point-free involution on these graphs which I will call *loop-switching*, given by adding a loop to every vertex that doesn't have one while simultaneously deleting the loops from all vertices that do. Then $\sqrt{F(x)}$ counts equivalence classes of graphs, where two graphs are in the same class if one can be obtained from the other by loop-switching a subset of its connected components. This follows from $\sqrt{F(x)} = \exp \frac{\log F(x)}{2}$ where $\log F(x)$ counts connected graphs and clearly on those the equivalence classes have size exactly 2. This also nicely explains why allowing loops is important here, and should work the same way in the multivariate version.


I guess to turn this into a "proper" combinatorial interpretation of $\sqrt{F(x)}$ as counting some class of structures of which a graph is formed from exactly two, one could somehow choose a canonical representative of each equivalence class on connected graphs. It seems like there is no good way to do this, however, since in some of those classes the two graphs are isomorphic.


