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


1. as a logical formula $\Phi= \bigwedge\_{i,j\in[n]} \neg\_{ij}\ Rx\_ix\_j$ with $\neg\_{ij} = \neg$ or $ \neg\neg$
2. 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:


1. $ \Phi' = \bigwedge\_ {i,j} \neg \neg\_{ij}\ R x\_i x\_j $
2. $\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?
> 
> 
> 



Isn't a graph to be considered isomorphic to its complement, actually?
It is a strange question, but maybe a useful answer can make it a bit better.


Certainly for many purposes a graph will look totally different from its complement. For instance, a graph and its complement have completely different spectra, diameter, perfect matchings, etc. So that side of the question is kind-of lame, I agree.


On the other hand, for some purposes a graph is much the same as its complement. One obvious case is when you are interested in the automorphism group of a graph, or in the computational problem of graph isomorphism. Then you might as well think of a graph as a bicoloring of the edges of a complete graph. It then has a natural extra automorphism given by switching the two colors. More generally a colored graph with $n$ colors is equivalent, for graph isomorphism and graph automorphism questions, to a complete graph with $n+1$ colors. This viewpoint is more useful than you might first think, because a natural partial algorithm and preparatory step in the graph isomorphism and automorphism problems is to recolor every vertex by its valence, then color every edge by the colors of its vertices, etc., until the recoloring process stabilizes. Many graphs can be completely identified this way in practice. Recognizing the equivalence between a graph and its complement makes it easier to understand what these algorithms are really doing.


Even some specific graphs, such as the Higman-Sims graph, are mainly used for their automorphisms and similar purposes, and it might be better to think of them as colorings of a complete graph.


A much deeper example is the [perfect graph theorem](http://en.wikipedia.org/wiki/Perfect_graph) of Lovasz. The theorem is that a graph is perfect if only if its complement is perfect. For perfect graphs, taking the graph complement is closely related to the dual or polar polytope of a convex polytope.


