3
$\begingroup$

Let's say that there exists a graph G. There exists an automorphism A that maps node n1 onto node n2. Does that imply there exists an automorphism that maps n1 onto n2 WHILE ALSO mapping n2 onto n1?

$\endgroup$
2
  • $\begingroup$ What have you tried? $\endgroup$ Commented Jun 13 at 5:39
  • 1
    $\begingroup$ Simple examples. Complete graphs. Trees. Every time I find 2 symmetric nodes, there exists some automorphism that swaps their position. $\endgroup$ Commented Jun 13 at 5:40

2 Answers 2

21
$\begingroup$

Counterexample: Take the graph with $12$ vertices $A,B,C,D,E,F,G,H,I,J,K,L$ and $15$ edges $AB,BC,CD,DE,EF,FG,GH,HI,IA,AD,DG,GA,CJ,FK,IL$. There is an automorphism of order $3$ which maps $J$ to $K$, but no automorphism swaps $J$ and $K$.

enter image description here

By the way, if we delete the vertex $L$, the resulting graph $\Gamma$ (with $11$ vertices and $14$ edges) is an example of something else: the vertices $J$ and $K$ are not symmetric (the graph $\Gamma$ has no nontrivial automorphism) although the subgraphs $\Gamma-J$ and $\Gamma-K$ are isomorphic.

$\endgroup$
2
  • 2
    $\begingroup$ +1 For an explicit example. You can save a few vertices by removing $J$, $K$ and $L$ and putting diagonals in the squares instead. $\endgroup$
    – Servaes
    Commented Jun 13 at 17:38
  • $\begingroup$ 20 years ago, the instant that I found out my father had died, the first thing I did was draw an example of a graph with that second property. I suppose I wasn't ready to deal with the emotional news, so my brain reverted to doing what comes most naturally to it, and solved a maths problem. $\endgroup$
    – tkf
    Commented Jun 13 at 19:04
8
$\begingroup$

Frucht's theorem states that every finite group is the group of symmetries of a finite undirected graph. Take any graph whhose group of automorphisms is, say, the cyclic group of order three, and it will have an automorphism taking some vertex $u$ to some vertex $v$, and an automorphism taking $v$ to $u$, but no automorphism taking $u$ to $v$ and $v$ to $u$.

https://en.wikipedia.org/wiki/Frucht%27s_theorem#

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .