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

automorphism-groupgraph theory

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

Best Answer

Welcome to MSE ^_^

Hint: Consider any of the following asymmetric graphs

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 ^_^

Related Solutions

[Math] Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

The degree sequence $\langle 3,3,2,2,2,2\rangle$ will work:

           *——*——*                *      *  
           |  |  |                |\    /|  
           *——*——*                | *——* |  
                                  |/    \|  
                                  *      *

[Math] prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

To prove that the graph doesn't have a cycle, note that we only have one vertex with degree greater or equal to $2$. Since in a cycle every vertex in it has a degree greater or equal to $2$ (since we have to both "enter" and "exit" the vertex) we can't have a cycle.

Best Answer

Related Solutions

[Math] Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

[Math] prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

Related Question