What is a simple to understand example (i.e. adjacency matrix) of a vertex transitive graph?

Question

I have a hard time understanding the intuition behind what a vertex transitive graph is. I was told that a circle graph on $10$ vertices is vertex transitive, but have been unable to generalize. The mathematical definition is unclear to me. Does anyone have a simple way of understanding it? Is there an example of an adjacency matrix representation of this?

Answer 1

In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.

Automorphisms

The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.

For a graph $X$, an automorphism of $X$ is a bijective function $\varphi: V(X)\to V(X)$ which has the property that $x,y\in V(X)$ are adjacent if and only if $\varphi(x)$ and $\varphi(y)$ are adjacent.

Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with $\{0,1,\dots, 9\}$ in order, going clockwise. An example of automorphism of this graph is $$\varphi: C_{10}\to C_{10} ~\text{ where }~ i\mapsto i+1\!\!\!\!\pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $\varphi$ is really just a rotation moving to the right by $2\pi/10$. Similarly, the automorphism $\psi: C_{10}\to C_{10}$ given by $\psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.

Vertex Transitivity

To apply this to vertex-transitivity, we first have the definition.

A graph $X$ is called transitive if for any pair of vertices $x,y\in V(X)$ there is some automorphism $\varphi$ such that $\varphi(x) = y$.

What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!

One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.

However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.

Examples

To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include

• Complete graphs
• Circulant graphs (which are general cycle graphs)
• Johnson graphs

with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.

Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.

Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'