2
$\begingroup$

Show that the Petersen graph is vertex transitive.

This is my first opinion to show that the Petersen graph is vertex transitive :

The vertices of the petersen graph $G$ are labeled with 2-element subsets of {$1,2,3,4,5$} and two vertices are adjacent if and only if their intersection is empty. This is the Kneser graph labelling (1955). So that $S_5$ is contained in Automorphisms and so Graph $G$ is vertex transitive. In fact automorphism of $G$ = $S_5$.

High appreciated if someone can explain it clearly.

$\endgroup$
  • $\begingroup$ You can also draw the Petersen graph and provide explicit maps, that map every vertex onto every other. This approach, too, can have an interesting effect: you see vertices move. Your approach above includes (for me at least) that the Petersen graph is isomorph to the construction process described. $\endgroup$ – Moritz Oct 31 '15 at 8:36
  • $\begingroup$ @Moritz can you explain to me with another way, sorry i still can not show that Petersen graph is vertex transitive. I appreciate any answer, guidance or reference. Thank you $\endgroup$ – user273952 Nov 1 '15 at 16:36
6
$\begingroup$

enter image description here

Consider the Petersen graph in the image on the left. I have labeled the vertices via sets, i.e., $12$ is $\{1,2\} = \{2,1\}$ and $34$ is $\{3,4\} = \{4,3\}$ et cetera. If you apply the permutation $(1,4,5,2,3)$ to the vertices, you get a clockwise rotation, that is, $(1,4,5,2,3)$ takes $\{1,2\}$ and maps it to $\{4,3\}$ and so on. The cycle notation $(1,4,5,2,3)$ means $1 \mapsto 4$ and $4 \mapsto 5$ and $5 \mapsto 2$ and $2\mapsto 3$ and $3\mapsto 1$. All you have to do now is the following: If you find a permutation which maps the inner $5$ vertices onto the outer $5$ vertices, the you are finished because then you can mix the two permutations to map every vertex onto every other. Still unclear?

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$
  1. Show that, for any permutation $\pi$ of the set $\{1,2,3,4,5\},$ there is an isomorphism of the Petersen graph which maps each vertex $\{x,y\}$ to $\{\pi(x),\pi(y)\}.$

  2. Show that, for any two vertices $\{x,y\}$ and $\{u,v\}$ of the Petersen graph, there is a permutation $\pi$ of $\{1,2,3,4,5\}$ such that $\pi(x)=u$ and $\pi(y)=v.$

  3. Conclude that the Petersen graph is vertex-transitive.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.