I don't understand some basic definitions in the setup for the following problem from Springer's Algebraic Combinatorics', and would love some clarification:
"For a simple graph Γ with vertex set V , we can define an automorphism of Γ to be a bijection ϕ: V → V such that u and v are adjacent if and only if ϕ(u) and ϕ(v) are adjacent. The automorphisms form a group under composition, called the automorphism group, Aut(Γ) of Γ.
Let Γ be a simple graph of 7 elements such that node 1 branches to nodes 2 and 3, and each of those branch to nodes 4 and 5 and nodes 6 and 7 respectively.
Let G be the automorphism group of Γ, so G has order eight."
My question (which I think will enable me to solve the actual problems relating to this setup) is, what are these 8 elements in G? I must be missing something basic, because I don't understand what one of these elements might look like (besides the identity of course, which would leave the graph alone). If you swapped nodes 6 and 7 (2 leaf nodes that share a parent) for example, you would get the same graph as before by any reasonable definition of a simple graph, right? I think I'm just missing something really basic here and am lost, so any help would be appreciated. (For the full problem, you can head to problem 7.1 on web pdf page #18 at http://math.mit.edu/~rstan/exer.pdf)
Thank you!
If you swap $6$ and $7$, you get "the same" graph, to be sure, but that just means that this is an automorphism! If your bijection $\phi$ leaves all vertices intact except it swaps $6$ with $7$, then it's certainly not an identity function on $V$, and yet clearly it's an automorphism according to the definition of an automorphism.
Think of a bijection of $V$ as a relabelling of vertices, and an automorphism is a way to relabel vertices so that edge relationships stay the same. Your problem was that you intuitively thought of relabelling that "doesn't change anything" as identity. But it isn't; it still moves vertices around; it's just an automorphism.
So your automorphisms are: