# does a graph with two vertices of the same degree automatically have a non-trivial automorphism

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?

• There are graphs with ALL vertices of the same degree that still have a trivial automorphism group (math.stackexchange.com/questions/227590/…) Dec 27, 2020 at 10:17
• 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.
– bof
Dec 27, 2020 at 10:56
• 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.
– bof
Dec 27, 2020 at 11:04
• 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.
– bof
Dec 27, 2020 at 11:09

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.