Let G be a graph which has the following properties:


1) For every $e\_1,e\_2 \notin E(G)$, $G \cup e\_1 \cong G \cup e\_2$ 


2) For every $e\_1,e\_2 \in E(G)$, $G\setminus e\_1 \cong G\setminus e\_2$


i.e. adding one more edge anywhere gives rise to the same graph and deleting one edge also gives rise to the same graph.


Let S be the set of graphs such that they are edge transitive and their complements are also edge transitive.
Does there exist a graph not in S which satisfies properties 1) and 2) ?



edge transitivity and edge deletion
There are no such graphs.


1. Consider the effect that edge addition and edge deletion have on the sum of the squares of the degrees. It shows that there are two constants $A,B$ such that for any two vertices $u,v$ we have $d\_u+d\_v=A$ if $uv\in E(G)$ and $d\_u+d\_v=B$ otherwise (where $d\_x$ is the degree of vertex $x$).
2. If there are three vertices of distinct degree, or if there are two vertices of one degree and two of another degree, it is impossible to put edges between them in such a way that the conclusion of step 1 is satisfied. Therefore, either $G=K\_{1,n}$ for some $n$, or $G$ is regular.
3. Since $K\_{1,n}$ and its complement are edge-transitive, we can assume $G$ is regular. Consider edges $e\_1=u\_1v\_1$ and $e\_2=u\_2v\_2$. Since isomorphisms preserve degree, any isomorphism from $G-e\_1$ to $G-e\_2$ maps $\lbrace u\_1,v\_1\rbrace$ to $\lbrace u\_2,v\_2\rbrace$. So it is an automorphism of $G$. Similarly for the complement of $G$.


Note that this proof is for **finite** graphs. I don't know what the situation is for infinite graphs.


