# Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them results in the same graph:

The two non-isomorphic edges here are colored red and blue. This is the smallest example of such graph and it is unique for 6 nodes.

I wonder what would be the smallest example of a graph with a triple of pairwise non-isomorphic edges and removal of any one of them resulting in the same graph.

UPDATE: user2097 below gave a construction for a graph on $(\tbinom{n}{2}+1)\cdot n$ nodes that squares the number of such pairwise non-isomorphic edges. When applied for the aforementioned graph on 6 nodes, it gives a graph on 96 nodes with a quadruple of pairwise non-isomorphic edges, removal of each of which results in the same graph. But it is probably not the smallest such graph.

• Do you know that such a graph and triple of edges exists? – Ben Barber Jul 17 '14 at 9:06
• @Ben Barber: Thanks to the construction proposed by user2097, we now know that such a graph exists. – Max Alekseyev Jul 31 '14 at 13:58

Let me give a construction that leads, for any fixed $N$, to a graph which has $N$ pairwise non-isomorphic edges and removal of any one of them results in the same graph. This is not a complete answer but I think it is of some interest.

Let us denote by $G$ a graph whose vertices are labeled with elements of a finite set $V$. We will assume that $\pi=\{p,q\}$ and $\rho=\{r,s\}$ is a non-isomorphic pair of edges in $G$. I will also assume that the graph $G'=G\setminus\pi$ (obtained from $G$ by removing $\pi$) is isomorphic to $G\setminus\rho$. For example, the 6-vertex graph from the initial question can be taken as $G$.

Let me construct the graph $\Gamma=\Gamma(G,\pi)$ as follows. The vertex set of $\Gamma$ will be the union of $V$ and $W\times V$; we denote the vertices from $W\times V$ as $v_{ec}$ for $e\in W$ and $c\in V$. (Here, $W$ stands for the set of all subsets of $V$ which have cardinality $2$.) The edges of $\Gamma$ are the following.

(1) there is an edge between $i$ and $v_{ec}$ if and only if $i\in e$;

(2) assuming $e\in G$, there is an edge between $v_{ex}$ and $v_{ey}$ if and only if $\{x,y\}\in G$;

(3) assuming $e\notin G$, there is an edge between $v_{ex}$ and $v_{ey}$ if and only if $\{x,y\}\in G'$;

(4) $\Gamma$ has only those edges which are specified in (1)-(3).

Speaking informally, we draw a copy of $G$ instead of every edge $\{i,j\}$. If $\{i,j\}$ is not an edge, we draw a copy of $G'$. In both cases, we draw the edges connecting all the new vertices with both $i$ and $j$. (We do this over all $\{i,j\}\in W$.)

Now, consider the edges $\{v_{\pi p},v_{\pi q}\}$, $\{v_{\pi r},v_{\pi s}\}$, $\{v_{\rho p},v_{\rho q}\}$, $\{v_{\rho r},v_{\rho s}\}$. From an informal description it can be seen that graphs obtained by removal of any one of them are isomorphic. To show that the edges provided are pairwise non-isomorphic, assume by contradiction that an automorphism $\psi$ of $\Gamma$ swaps some pair of them. Then,

(1) a vertex $v_{ec}$ can not be an image $\psi(i)$ of $i$ under $\psi$ because they have different degrees;

(2) then, denoting $e=\{i,j\}$ and $\psi(e)=\{\psi(i),\psi(j)\}$, we conclude $\psi(v_{ec})=v_{\psi(e)c'}$ for some $c'$;

(3) the subgraphs generated by all $v_{ec}$ and by all $v_{e'c}$ (in both cases, $c$ runs over $1,\dots,n$) are isomorphic iff either $e,e'\in G$ or $e,e'\notin G$, therefore $\{\psi(i),\psi(j)\}\in G$ iff $\{i,j\}\in G$;

(4) this shows that $\psi'$, the restriction of $\psi$ to $\{1,\ldots,n\}$, is an automorphism of $G$;

(5) by the definition of $G$, $\psi'$ can not swap $\pi$ and $\rho$, so that $\psi(\pi)=\pi$ and $\psi(\rho)=\rho$;

(6) then, the restriction of $\psi$ to $v_{\pi c}$ is an automorphism, which cannot swap $\{v_{\pi p},v_{\pi q}\}$ and $\{v_{\pi r},v_{\pi s}\}$ again by definition of $G$;

(7) similarly to the previous step, $\psi$ cannot swap $\{v_{\rho p},v_{\rho q}\}$ and $\{v_{\rho r},v_{\rho s}\}$;

(8) finally, $\psi$ can not swap $v_{\rho a}$ and $v_{\pi b}$ because of step (5).

Let me finally note that we can apply the $\Gamma$ construction to $\Gamma_0=\Gamma(G,\pi)$ itself. As far as I can see, the graph $\Gamma_1=\Gamma(\Gamma_0,\{v_{\rho p},v_{\rho q}\})$ has $16$ pairwise non-isomorphic edges and removal of any one of them results in the same graph. Similarly constructed $\Gamma_2$ will have $256$ edges with this property, and so on.

• Does this really lead to a construction for "any" fixed N? Maybe I am misunderstanding the intent of the first sentence. – j.c. Aug 20 '14 at 10:29
• @j.c. I meant that, given an integer $N$, one is able to construct a graph which has $N$ pairwise non-isomorphic edges such that removal of any one of them results in the same graph. In particular, if the result is true for some $N_0$, then it is true for any $N<N_0$; this is why it is sufficient to consider $N$ which are powers of $2$. – user56203 Aug 20 '14 at 22:08

This is essentially a comment on user2097's excellent answer. One consequence of that answer was the construction of a graph with four non-isomorphic edges whose removals result in isomorphic graphs. The graph so constructed had 96 nodes and 293 edges.

Without changing the idea of their construction, various tricks allow an improvement to a graph with the same property with 24 nodes and 47 edges.

The tricks used are:

1. Instead of connecting the nodes $i$ to nodes $v_{ec}$ whenever $i$ is in $e$, do this whenever $i$ is in $e$ and $c$ is in some set of vertices stable under the isomorphism of subgraphs.

2. Instead of replacing all edges with a copy of $G$ or $G'$, only do this for enough edges in the complete graph to contain the two special edges and be stable under the isomorphism of subgraphs.

To wit, begin with the graph described by the original poster:

Replace the solid green edges with a copy of $G$ as follows:

Replace the dotted green edge with a copy of $G$ without one of its special edges:

The final result is as promised.

It is not hard to see by starting at the 1-valent vertices that this graph has no automorphisms.

• This is very neat and makes me wonder (again!) what would be the smallest graph with a triple of such non-isomorphic edges. Now we know that it has at least 11 and at most 24 vertices. – Max Alekseyev Aug 24 '14 at 16:33

Not an answer, just an extended comment.

For $n \leq 10$ such graph does not exists.

I am currently checking $n = 11.$ Are there any structural properties that such a graph has, other than it is connected and not (in particular) edge-transitive ?

Following is a simplified Sage program used for the checking in case anyone wants to play with it

def edgeOrbits(G):
# Gap expects us to send a permutation group acting on 1,...,n
G.relabel({i:i+1 for i in G})
A,o = G.automorphism_group(order=True)
if o == 1: return G.edges(labels=false)
E = str([ [x,y] for x,y in G.edges(labels=false)])

G.relabel({i:i-1 for i in G})
return [(int(x)-1,int(y)-1) for x,y in gap("List(Orbits("+str(A._gap_())+"," + str(E) + ",OnSets), x->x[1]);")]

# Returns edges x,y,z so that G-x,G-y,G-z are isomorphic
# yet the edges x,y,z are not mapped by an aumorphism of G,
# or false if G has no such edges.
def isNice(G):
cann = {}
for e in edgeOrbits(G):
G.delete_edge(e)
s = G.canonical_label().graph6_string()
if s not in cann:
cann[s] = [e]
else:
cann[s] += [e]
if len(cann[s]) >= 3:
return cann[s]

return false

# Find a graph with the stated property
def findGraph(n):
for G in graphs.nauty_geng(str(n) + " -c"):
t = isNice(G)
if t:
print G.graph6_string(),t

• Is edgeOrbits(G) supposed to return all pairwise non-isomorphic edges? Then it fails to do so in the following example: edgeOrbits(Graph([(0, 1), (0, 2), (1, 2), (2, 3)])) which returns [(0, 1), (0, 2)], while there should be also edge (2,3). – Max Alekseyev Jul 16 '14 at 22:14
• @MaxAlekseyev Thanks for spotting that out. I wanted to restrain myself from using the more complicated version of EdgeOrbits that I have now included in the answer. I am now wondering for which graphs is the previous EdgeOrbits not correct. – Jernej Jul 17 '14 at 7:57
• Did you re-check the graphs on $n\leq 10$ nodes with the new edgeOrbits function? – Max Alekseyev Jul 17 '14 at 13:23
• @MaxAlekseyev I think for graphs with $\delta \ge 2$ the property still holds (orbits acting on the edge sets = orbits of line graph) and I've checked only for $\delta < 2.$ See also mathworld.wolfram.com/Edge-TransitiveGraph.html where this claim is implicitly made in the definition of edge-transitive graphs – Jernej Jul 17 '14 at 20:19