Consider a finite simple graph $G$ with $n$ vertices, presented in two different but equivalent ways:

- as a logical formula $\Phi= \bigwedge_{i,j\in[n]} \neg_{ij}\ Rx_ix_j$ with $\neg_{ij} = \neg$ or $ \neg\neg$
- as an (unordered) set $\Gamma = \lbrace [n],R \subseteq [n]^2\rbrace$

In each case the complement $G'$ of $G$ is easily presented and is of course *not* isomorphic to $G$ (in the usual sense) generally:

- $ \Phi' = \bigwedge_ {i,j} \neg \neg_{ij}\ R x_i x_j $
- $\Gamma' = \lbrace [n],[n]^2 \setminus R\rbrace$

Let's state for the moment that the presentation as a logical formula is the more "flexible" one: we can easily omit single literals, leaving it open whether $Rx_ix_j$ or not. But this can be mimicked for set presentation by making it from a pair to a triple $\lbrace[n],R,\neg R \subseteq [n]^2 \setminus R\rbrace$.

Let's call a presentation *complete*, if it leaves nothing open, i.e. no omitted literal and $\neg R = [n]^2 \setminus R$, resp.

Now, let a graph be given in complete set presentation $\lbrace[n],R,\neg R = [n]^2 \setminus R\rbrace$. Since order in this set should not matter, any sensible definition of "graph isomorphism" should make any graph isomorphic to its complement.

Where and how do I run into trouble when I assume - following this line of reasoning, contrary to the usual line of thinking - that every (finite) graph is isomorphic to its complement?

yourobject and its natural notion of isomorphism is the only sensible one is, well, silly. – Mariano Suárez-Alvarez♦ Mar 2 '10 at 1:45