For a graph $G = (V,E)$ and an element $v \in V, G\backslash v$ denotes the subgraph of $G$ induced by $V\backslash v.$ Find, with proof, an example of a graph $G = (V,E)$ and two vertices $v, w \in V$ with the following properties:

  • the subgraphs $G\backslash v$ and $G\backslash w$ are isomorphic but
  • there is no automorphism $f$ on $G$ so that $f(v) = w.$

I'm not sure how to find this graph. I think it's relatively easy to find a graph $G$ and two vertices $v$ and $w$ so that $G\backslash v$ and $G\backslash w$ are isomorphic (the cycle $C_4$ and any two distinct vertices should suffice). For the cycle $C_4,$ one could just choose two vertices $v$ and $w$ diagonal from each other and define an automorphism that maps $v$ to $w$ and $w$ to $v$ and the other two vertices to themselves, so the cycle $C_4$ clearly doesn't satisfy the constraints. I'm not sure how to find a graph so that there is no automorphism (isomorphism from a graph to itself) $f$ on $G$ so that $f(v) = w.$ I think it might be useful to show that no such automorphism exists using some sort of contradiction involving two vertices $v$ and $w$ being adjacent in $G$ but $f(v)$ and $f(w)$ not being adjacent.


Hint: I found this problem a lot easier when I considered examples where $v$ and $w$ could be cut vertices (so $G-v$ is disconnected).

For an example graph, click the spoiler below:

enter image description here

By the structure of the graph, it should be easy enough to show that no automorphism carries $v$ to $w$.

EDIT: For a proof that no automorphism carries $v$ to $w$, let $v$ be the left black vertex and $w$ the right one. Automorphisms preserve every graph theoretic feature of the graph, so they preserve the number of neighbours of given degree at a given distance. Per bof's comment, $w$ is distance $2$ from two vertices of degree $1$, while $v$ is distance two from $1$ vertex of degree $1$, therefore no automorphism carries $v$ to $w$.

  • $\begingroup$ thanks for the explanation $\endgroup$
    – user747916
    Oct 20 '20 at 16:06

This is my favorite example, though it's far from the smallest. It has $11$ vertices $p,q,r,s,t,u,v,w,x,y,z$.

Start by drawing a triangle with edges $pq,qr,rp$.

Next draw a square on each side of the triangle, making a figure like Pythagoras' Pants: $ps,st,tq,qu,uv,vr,rw,wx,xp$.

Finally add two leaves $ty,vz$.

The graphs $G-y$ and $G-z$ are isomorphic, but no automorphism of $G$ maps $y$ to $z$.

In fact, $G$ has no nontrivial automorphisms. First note that $G$ has just $3$ vertices of degree $4$, namely $p,q,r$. Of these, $q$ is unique with the property that the two vertices of degree $1$, namely $x$ and $y$, can be connected by a path that passes through $q$ but no other vertex of degree $4$. Therefore any automorphism of $G$ must fix $q$. Next, since $x$ and $y$ are the only vertices of degree $1$, and since $d(q,x)=3$ and $d(q,y)=2$, the automorphism must fix $x$ and $y$ as well. Now it is quite straightforward to show that all the other vertices must be fixed.

The smallest example has $8$ vertices and $9$ edges. Draw a $6$-point path $s—t—u—v—w—x$; add a vertex y joined to $s$ and $t$, and a vertex $z$ joined to $u$ and $v$. The graphs $G-t$ and $G-v$ are isomorphic, but there is no automorphism of $G$ that maps $t$ to $v$.

Any automorphism of $G$ must fix $x$, the only vertex of degree $1$. Since $d(x,v)=2$ and $d(x,t)=4$, $t$ and $v$ must be fixed as well. In fact, any automorphism of $G$ must fix all vertices except possibly $s$ and $y$ which may be swapped.

  • $\begingroup$ Very nice answer @bof , I was wondering if there was such an example if $G \setminus \{v\}$ was connected. $\endgroup$
    – Mike
    Oct 19 '20 at 17:27
  • $\begingroup$ Thanks, but I was looking for some more justification as to why there's no such automorphism. For instance, there cannot be an automorphism that maps vertices of different degrees to each other, and automorphisms must preserve the degree sequences of neighbours. $\endgroup$
    – user747916
    Oct 19 '20 at 18:24
  • $\begingroup$ @Mike If $G-v$ is disconnected, can't you just make a new graph $H=G+x$ where the new vertex $x$ is joined to every vertex in $G$? Then $H-u$ and $H-v$ are connected and are isomorphic to each other, and any automorphism of $H$ must fix $x$, so it's an automorphism of $G$ and can't map $u$ to $v$. $\endgroup$
    – bof
    Oct 19 '20 at 23:18
  • $\begingroup$ @user3472 I added more details as requested. $\endgroup$
    – bof
    Oct 20 '20 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy