3
$\begingroup$

It is everywhere, but I cannot see it from scratch. For example the graph $K_{1,3}$ given here (p23), it is easy to see why it is edge-transitive and not vertex-transitive. The definition given in Algebraic Graph Theory (Godsil) is:

A graph $G$ is edge transitive if its automorphism group acts transitively on $E(G)$.

The Petersen graph has $S_5$ as its automorphism group. The brute force approach will be to prove that all $S_5$ acts transitively on the edge set, but it is very tedious, right? Is there an easy way to see the edge transitivity?

Improve this question
$\endgroup$
  • $\begingroup$ No. ${}{}{}{}{}$ $\endgroup$ – Mariano Suárez-Álvarez May 16 '15 at 0:29
  • $\begingroup$ Maybe it's possible to prove this from the fact that the Petersen graph is the dodecahedral graph with opposite vertices identified (so, it's like a projective version of the Platonic dodecahedron). I doubt such an approach would be "easy", exactly, but it might yield some more visual sense of the symmetries involved. $\endgroup$ – user21467 May 16 '15 at 1:16
5
$\begingroup$

Looking at the standard picture for the Petersen graph, it is clear that the automorphism group acts transtitively on the edges of exterior pentagon, on the edges of the inner star, and on the edges of connecting the two. It is enough then to find an isomorphism mapping one of the outer edges to one of the edges in the star and one mapping it onto one of the middle edges.

So it all comes down to finding those two automorphisms.

Notice that this is the brute force approach —which is not that tedious.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Before posting the question I did the following edge automorphism, $e_1 \rightarrow e_{11} , e_2 \rightarrow e_{12}, e_3 \rightarrow e_{13}, e_4 \rightarrow e_{14}, e_5 \rightarrow e_{15}$ (this edges are of the outer and inner $C_5$, and the remaining edges: $e_{6,7,\dots,9}\rightarrow e_{6,7,\dots,9}$ (the ones that join every outer and inner $C_5$). So with what you say, this is enough to prove edge-transitivity. $\endgroup$ – user2820579 May 16 '15 at 0:47
  • $\begingroup$ Cutting the brute force in half, you only need to find one automorphism, which maps an outer edge to a middle edge, and maps another outer edge to an inner edge. Hard to avoid, really. It's clear from looking at the picture that an automorphism which maps a middle edge to an inner edge can't leave the set of outer edges fixed, some outer edge must get mapped to a middle or inner edge. So all edges are equivalent. $\endgroup$ – bof May 16 '15 at 5:05
7
$\begingroup$

Regard the Petersen graph as the Kneser graph $KG_{5,2}$: that is, the graph whose vertices are 2-element subsets of $\{1,2,3,4,5\}$, with an edge between any two vertices which are disjoint as subsets. (The easy way to see that this corresponds to the standard "star" picture for the Petersen graph is to put all the sets of the form $\{a,a+1\}$ in the outer pentagon, and all the sets of the form $\{a,a+2\}$ in the inner star, with all addition performed $\bmod 5$.)

Now, each edge of the Petersen graph corresponds to a pair of disjoint 2-element subsets of $\{1,2,3,4,5\}$. As $S_5$ acts transitively on all such pairs, the Petersen graph is edge-transitive.

Improve this answer
$\endgroup$
0
$\begingroup$

You can obtain the Petersen graph from the dodecahedral graph (aka. the edge graph of the dodecahedron) by identifying antipodal vertices (vertices of maximal mutual distance). One also say, that the dodecahedral graph double covers the Petersen graph.

The dodecahedron is famously known to be a regular polytope, i.e. its symmetry group acts transitively on its vertices, edges and faces. The Petersen graph inherits the edge-transitivity via the covering from the dodecahedral graph.

See also "hemi dodecahedron".

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.