0
$\begingroup$

Hi I am trying to proof that all graphs with 4 vertices have a non-trivial automorphism group. I constructed a two case proof (connected and unconnected graphs) and said that if at least two vertices have the same degree the graph has a non-trivial automorphism since those two vertices can swap.

I realise this is wrong as this does not necessarily maintain the adjacency of the graph but don't know how else I would complete this proof?

any advice would be appreciated

$\endgroup$
4
  • 1
    $\begingroup$ There are graphs with ALL vertices of the same degree that still have a trivial automorphism group (math.stackexchange.com/questions/227590/…) $\endgroup$
    – xxxxxxxxx
    Dec 27, 2020 at 10:17
  • 2
    $\begingroup$ Since every graph with more than one vertex has two vertices with the same degree, your conjecture would imply that every nontrivial graph has a nontrivial automorphism. $\endgroup$
    – bof
    Dec 27, 2020 at 10:56
  • 1
    $\begingroup$ Do you mean simple undirected graphs? In that case, since there are only $11$ different graphs with $4$ vertices, you could just do a proof with $11$ cases, by exhibiting a nontrivial automorphism for each graph. Since a graph and its complement have the same automorphisms, you can cut the work in half to just $6$ cases. If a graph has two isolated vertices they really can be swapped; using that leaves you with only $4$ cases. $\endgroup$
    – bof
    Dec 27, 2020 at 11:04
  • 1
    $\begingroup$ By the way, since you mentioned connected and disconnected graphs, it would be enough to show that every connected graph on $4$ vertices has a nontrivial automorphism. If a graph is disconnected, then its complement is connected, and has exactly the same automorphisms. $\endgroup$
    – bof
    Dec 27, 2020 at 11:09

1 Answer 1

1
$\begingroup$

Welcome to MSE ^_^

Hint: Consider any of the following asymmetric graphs

asymmetric graphs from wikipedia

Notice each of these has two vertices of the same degree, yet none of them have any nontrivial automorphisms (do you see why?). The idea is that it's not enough to swap two vertices $x$ and $y$. To be an automorphism we must the swap things next to $x$ with things next to $y$. But there might be some obstruction at this next stage. Or, similarly, at some stage many vertices away from $x$ and $y$. There is a more detailed explanation for the top left graph above below the fold, but you should try to work it out yourself too.

In the top left graph, for instance, we can't swap the two vertices of degree $1$ because we would then be forced to swap their (unique!) adjacent vertices too. Yet the two adjacent vertices have different degrees, and so cannot be swapped. Every such graph has a similar argument.


I hope this helps ^_^

$\endgroup$

You must log in to answer this question.

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