Removal of non-isomorphic edges results in the same graph

Question

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.

P.S. See also sequence https://oeis.org/A245246 -- extension is welcome.

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.

Answer 1

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.

Answer 2

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.

Answer 3

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()
        G.add_edge(e)
        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