How can I show/understand a graph is vertex-transitive?

Solution 1:

1. This statement is true. This is essentially saying the graph has rotational symmetry. That is, if you rotate the graph by moving vertex $1$ to vertex $2$, and so on until you get to vertex $n$ which you move back to $1$ you'll end up with the same graph. Clearly you can keep rotating to move one vertex to any other vertex.

2. This statement is false. This requires that the graph be rotationally symmetric. Not only that, you a declaring that a very specific rotation works. The one way where you send vertex $1$ to $2$ and so on. The problem here is even if the graph is rotationally symmetric, if you reorder the vertices the permutation specified by that $P$ may not work. For example imagine a square with vertices reading clockwise 1,3,2,4. The permutation 1->2->3->4->1 no longer preserves the edges of the graph. You'd need to do 1->3->2->4->1 which corresponds to a different matrix. (same as $P$ with the middle two columns swapped).