Graph $G$ such that removing an edge leaves $G$ "unchanged" Is there an infinite simple, undirected graph $G = (V,E)$ such that there is $e\in E$ such that $G \cong (V, E\setminus\{e\})$?
(There cannot be a finite graph with that property because removing an edge changes the degree sequence.)
 A: I report as an answer what I wrote in the comments. The random graph is an example of a connected graph with this property, see the survey. It even has the property that for every $e \in E$, $G$ is isomorphic to $(V,E\setminus \{e\})$ (see Proposition 2 in that survey).
The random graph, introduced by Erdös and Rényi, is the unique graph (up to isomorphism) on a countably infinite vertex set $V$ with the property that for any finitely many distinct vertices $u_1,\dots,u_n,v_1,\dots,v_m$, there is a vertex that is adjacent to all $u_i$'s but to none of the $v_j$'s.
What is intriguing about it is that it appears in many different ways. In particular, and this is the reason for the name, if you draw an edge between any pairs of vertices independently at random with probability $\frac 1 2$, almost surely the graph you obtain is the random graph.
A: Take the graph with the integers as its vertex set and with edges {n, n+1} for all n>=0. Now remove the edge {0,1}
A: Let $V=\{Fred\}\cup\mathbb N$.  Let $E=\{(Fred,p^3)\mid p \text{ is a prime }\}$.
A: An infinite path, the "left half" of its vertices is glued to triangles, the "right half" is glued to paths of length two.
You can remove an edge from one of the triangles without changing the graph.

A: How about a graph $G=(V,E)$ consisting of infinitely many isolated vertices and infinitely many disjoint edges.  Like the random graph it has the property that for all $e\in E$, $G\simeq (V, E\setminus \{e\})$.
