3
$\begingroup$

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.)

$\endgroup$
16
  • 4
    $\begingroup$ An(other) example is the random graph arxiv.org/abs/1301.7544 $\endgroup$ Commented Jul 27, 2021 at 21:08
  • 7
    $\begingroup$ @MarkSapir The graph with no edges isn't such an example, because there is no edge to remove in the first place. $\endgroup$
    – user44191
    Commented Jul 27, 2021 at 21:21
  • 2
    $\begingroup$ @MarkSapir Yes, it is connected: better, any two points have a common neighbour. $\endgroup$ Commented Jul 27, 2021 at 21:48
  • 3
    $\begingroup$ @MarkSapir The random graph is characterized up to isomorphism, among countable simple graphs, by the property that, given any two disjoint, finite sets of vertices $A$ and $B$, there exists another vertex adjacent to all the members of $A$ and to none of the members of $B$. This property is easily seen to be preserved when an edge is removed. $\endgroup$ Commented Jul 28, 2021 at 1:20
  • 2
    $\begingroup$ The random graph property implies that for any such $A$ and $B$, there are infintely many vertices each of which is connected to all elements of $A$ and to no elements of $B$. Removing an edge can disturb at most one of them, hence infinitely many remain. $\endgroup$ Commented Jul 28, 2021 at 5:44

5 Answers 5

14
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ So this is the Rado graph, right? It's an initially surprising fact that the Rado graph with probability $\frac12$ is almost surely isomorphic to the Rado graph with probability 0.85932895347895738927235887234 $\endgroup$ Commented Jul 27, 2021 at 22:14
  • 2
    $\begingroup$ One thing about the random (or Rado) graph is that every vertex has infinite degree, which might not be desirable from the OP's perspective. $\endgroup$ Commented Jul 27, 2021 at 22:15
  • 3
    $\begingroup$ On the other hand, it is easy to see that if $G$ is a connected graph with the property that for every edge $e\in E$, $G$ is isomorphic to $G\setminus \{e\}$, then indeed every vertex must have infinite degree (otherwise you can repeatedly delete edges from around a vertex of finite degree to isolate it, contradicting the connectedness assumption). $\endgroup$ Commented Jul 27, 2021 at 22:16
5
$\begingroup$

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}

$\endgroup$
6
  • 1
    $\begingroup$ When you remove an edge, you leave its endvertices. So the graph you get will be disconnected. $\endgroup$
    – markvs
    Commented Jul 27, 2021 at 21:04
  • 1
    $\begingroup$ it was disconnected to begin with... $\endgroup$
    – hbjj
    Commented Jul 27, 2021 at 21:06
  • 2
    $\begingroup$ I am sure the OP meant a connected graph but forgot to add this condition. $\endgroup$
    – markvs
    Commented Jul 27, 2021 at 21:07
  • 6
    $\begingroup$ Then take ${\mathbb Z} \times \{0,1\}$, with "horizontal" edges $((n,i), (n+1,i))$ for all $n$ and $i$, and "vertical" edges $((n,0),(n,1))$ for $n \ge 0$. This is connected. And remove the first vertical edge $((0,0),(0,1))$. $\endgroup$ Commented Jul 27, 2021 at 21:15
  • 4
    $\begingroup$ To add to @hbjj's example, you could make it connected simply by adding one vertex that connects with everything, and make it a fixed point for the isomorphism. $\endgroup$
    – user44191
    Commented Jul 27, 2021 at 21:44
2
$\begingroup$

Let $V=\{Fred\}\cup\mathbb N$. Let $E=\{(Fred,p^3)\mid p \text{ is a prime }\}$.

$\endgroup$
1
$\begingroup$

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\})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.