Determine all possible automorphisms of a graph

2.3k Views Asked by At

Let $G$ be the undirected graph whose vertex set is $\{a,b,c,d,e\}$ and edge set $\{ab, ae, bc, be, cd, ce, de\}$. The graph is drawn below:

Drawing of the graph G

Let $V$ denote the set of vertices of the graph G defined. Determine all possible isomorphisms $\varphi:V\:\:\xrightarrow{}\:V$ from the graph $G$ to itself that satisfy $\varphi(b)=c.$


Ok, so I know what a graph isomorphism is and how to check if a graph is isomorphic what is puzzling me is how to determine all of the possible isomorphisms and also the $\varphi(b)=c$ part does that just mean redraw the graph interchanging b and c?

1

There are 1 best solutions below

2
On BEST ANSWER

No. You need to find all maps (in fact permutations) $f\colon V\to V$ such that $f(b)=c$ and whenever $xy$ is an edge then also $f(x)f(y)$ is an edge.

You can argue as follows: $a$ is a neighbour of $b$ and has degree $2$, hence $f(a)$ must be a neighbour of $f(b)=c$ and must also have degree $2$. This implies $f(a)=d$. Similarly $f(d)=a$ and thus par force $f(e)=e$. We conclude that there is only one such isomorphism.