If we consider the dihedral group of order 12, $G = \langle a, b \mid a^2 = b^2 = (ab)^6 = e \rangle$, then the Cayley graph corresponding to $\{ a, b \}$ is the cyclic graph on 12 vertices with edges labeled alternately by $a$ and $b$. We may then consider $H_1 = G \times \mathbb Z/2 \mathbb Z$ and $H_2 = G \rtimes \mathbb Z/2 \mathbb Z$ where the copies of $\mathbb Z/ 2 \mathbb Z$ are generated by $c$ and $d$ respectively, and where $d$ acts by $d a d = b$, $d b d = a$. Then the Cayley graph of $H_1$ with respect to $\{ a, b, c \}$ consists of two copies of cyclic graphs of order 12 with edges labeled by $c$ connecting the two graphs. Since $d$ just interchanges $a$ and $b$ we have that the Cayley graph of $H_2$ with respect to $\{ a, b, d \}$ can be obtained from the Cayley graph of $H_1$ by just relabeling the second copy of the cyclic graph, so that the two Cayley graphs will be isomorphic.
Unfortunately, the generating set for $H_2$ is not minimal since by the definition of $d$ we have $b \in \langle a, d \rangle$. This can be fixed however by taking two automorphisms $c$ and $d$ which are complicated enough so that this doesn't occur.
Specifically, we can let $c$ act on $G$ by $cac = ababa$, and $cbc = babab$, and we can let $d$ act on $G$ by applying $c$ and then interchanging $a$ and $b$, i.e., $dad = babab$, and $dbd = ababa$. It's not hard to see that these indeed define order two automorphisms of $G$, and for the same reason as above we have that the Cayley graphs of $H_1$ and $H_2$ will be isomorphic.
It is also not hard to check that we now have $| \langle a, c \rangle | = | \langle b, c \rangle | = 12 < 24$ and $| \langle a, d \rangle | = | \langle a, d \rangle | = 8 < 24$ so that the generating sets are now minimal. Moreover, the groups $H_1$ and $H_2$ will not be isomorphic, this can be seen for instance by counting the number of elements of order 2, (I counted 15 for $H_1$ and 9 for $H_2$, but I've omitted the tedious details).
I don't see the equivalence to the travelling salesman problem. I think the following works for acyclic networks:
Split every node $v$ except start and end node into two copies $v^-$ and $v^+$, and add the arcs $(v^-,v^+)$. An arc $(v,w)$ of the original network is replaced by the arc $(v^+,w^-)$ with cost equal to the cost of $(v,w)$. Then your problem should be equivalent to finding a min cost flow with upper and lower capacity equal to one for the arcs of the form $(v^-,v^+)$.
Best Answer
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.