Number of connected labeled graphs (mod 2) Let  $c(n)$  denote the number of connected vertex labeled
graphs on  $n$  vertices.  For example,  $c(3) = 4$.  The 
sequence begins
$$
1, 1, 4, 38, 728, 26704, \ldots
$$ 
It is straightforward to show by, say, the use of generating
functions or Möbius functions that $c(n)$ is  an even number
for all $n$ at least three.
Question:  Can one prove the above parity result by explicitly
exhibiting a pairing on the set of connected vertex labeled graphs?
 A: Let $V$ be the vertex set, $|V|=n\ge3$, and choose $x,y\in V,x\ne y$. Divide the connected graphs $G$ with $V(G)=V$ into three disjoint classes according as:
(I) $xy\not\in E(G)$;
(II) $xy\in E(G)$ and $G-xy$ is connected;
(III) $xy\in E(G)$ and $G-xy$ is disconnected.
The graphs in class (I) can be paired with the graphs in class (II) by adding or subtracting the edge $xy$.
Swapping $x$ and $y$ defines an involution in class (III); this involution has no fixed points because of our assumption that $n\ge3$.
A: Let $\mathcal{C}_n$ be the set of $n$-vertex connected graphs with $n \geq 3$ on the vertex set $\{v_i\}_{i=1}^n$.
We act on $\mathcal{C}_n$ by the group generated by the $2$-cycle $\alpha:=(v_1 v_2)$ [i.e. this action swaps the vertex labels $v_1$ and $v_2$].  By the Orbit-Stabiliser Theorem, orbits under this action have size $2$ unless $\alpha$ is an automorphism of the graph in the orbit.  This pairs up all graphs in which $\alpha$ is not an automorphism.
The graphs in an orbit of size $2$ in the $n=3$ case is drawn below:

If $\alpha$ is an automorphism of $G \in \mathcal{C}_n$, we pair $G$ up with the graph with the edge $v_1v_2$ toggled.  Since $\alpha$ is an automorphism $v_1$ and $v_2$ have the same neighbourhood (and since $G$ is connected and $n \geq 3$, this neighbourhood is non-empty).  This pairs up all graphs in which $\alpha$ is an automorphism.
The following two graphs belong to orbits of size $1$; here we instead pair them up by adding/deleting the edge $v_1v_2$.

In fact, the above drawings list all the graphs in the $n=3$ case.
