# What is a vertex-transitive graph? (Question about Lovász Conjecture)

I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below).

$$\bullet$$ It states that a graph is vertex-transitive if for any two vertices $$u$$ and $$v$$ of the graph, there is some automorphism (i.e. a relabeling of vertices of a graph) $$f: V(G)\rightarrow V(G)$$ where $$f(u)=v$$.

$$\textbf{QUESTION:}$$ I'm having a hard time figuring out how to use this definition in this context; so, my question is why are certain graphs vertex transitive and others not? For example, what is the function for the graph below that makes it vertex transitive?

• It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on. – Wojowu Mar 9 at 16:57

Suppose you wanted to swap $$v_1$$ and $$v_2$$. Then, you could leave $$v_3$$ and $$v_4$$, and all of the connections in the graph would be the same (e.g. the new $$v_1$$ and the old $$v_1$$ are both still connected to the vertices labelled $$v_2,v_3,v_4$$). This graph is $$K_4$$ which is particularly nice in that any rearrangement preserves that property.
• That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f=\{ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)\}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before? – W. G. Mar 9 at 17:40
• No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 \rightarrow v_2$, $v_2 \rightarrow v_1$, $v_3 \rightarrow v_4$ and $v_4 \rightarrow v_3$. – Michael Biro Mar 9 at 17:48