[Math] A proof about Petersen Graph

graph theory

I want to introduce you one of my midterm question in Graph Theory. I could not do this question in my exam and i wonder how to do that.

Prove that every edge in the Petersen Graph belongs to exactly 4 5-cycles, and use this to show that the Petersen Graph has exactly 12 5-cycles.

Girth of a Petersen Graph 5.

(Another question in my mind is below.

We know Petersen graph has 120 automorphism.

Is there any relationship between the being 12 5-cycle and having 120 automorphisms such that a cycle has 2n automorphisms

n : number of vertices in the graph.

So we, have 12 cyle * 5 length of the cycle * 2 = 120 automorphisms ? )

I want to learn the proof of my midterm question. Could you please help ?

Best Answer

It's convenient to work with the Kneser graph interpretation of the Petersen graph: its vertices are the pairs $$\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}$$ and its edges join the pairs that don't intersect. (For example, $\{1,2\}$ is adjacent to $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$.)

To show that every edge is contained in four $5$-cycles, we prove this for the edge between $\{1,2\}$ and $\{3,4\}$. (This is fine to assume because the Petersen graph is edge-transitive: there is an automorphism sending every edge to this edge.) Then the remainder of the cycle can be chosen as follows:

  • The other neighbor of $\{1,2\}$ in the cycle must be $\{x,5\}$ for some $x\in\{3,4\}$.
  • The other neighbor of $\{3,4\}$ in the cycle must be $\{y,5\}$ for some $y \in\{1,2\}$.
  • The leftover vertex of the cycle must be disjoint from both $\{x,5\}$ and $\{y,5\}$, so it can only be the complement $\{1,2,3,4\} \setminus \{x,y\}$.

Altogether, we have two choices for $x$ and two choices for $y$, so the cycle can be chosen in four ways. We can list out the options: they are

  • $\{1,2\}, \{3,4\}, \{1,5\}, \{2,3\}, \{4,5\}$,
  • $\{1,2\}, \{3,4\}, \{1,5\}, \{2,4\}, \{3,5\}$,
  • $\{1,2\}, \{3,4\}, \{2,5\}, \{1,3\}, \{4,5\}$,
  • $\{1,2\}, \{3,4\}, \{2,5\}, \{1,4\}, \{3,5\}$.

Finally, if each of $15$ edges is contained in four $5$-cycles, that gives $15 \cdot 4 = 60$ cycles total; but each cycle is counted $5$ times, once for each of its edges, so the Petersen graph contains $\frac{60}{5} = 12$ cycles.

You also ask if there is a connection between the Petersen graph having $12$ $5$-cycles, a $5$-cycle having $10$ automorphisms, and the Petersen graph having $12 \cdot 10$ automorphisms.

This is certainly not a general rule for all graphs that we can count automorphisms this way. It works for the Petersen graph because it is highly symmetric. We can obtain all $120$ automorphisms as follows:

  • Pick any of the $12$ cycles, and decide to map our favorite cycle $\{1,2\}, \{3,4\}, \{5,1\}, \{2,3\}, \{4,5\}$ onto the one we picked.
  • Because a cycle has $10$ automorphisms, there are $10$ ways to do this.
  • This determines where we send the five vertices of our favorite cycle, and this partial automorphism can be completed to a unique automorphism of the Petersen graph.

It is this "can be completed to a unique automorphism" bit that won't work in general. In other graphs, this can fail in a couple of ways:

  1. Consider the disconnected graph made up of two $5$-cycles with no edges between them. This has $2 \cdot 10 \cdot 10$ automorphisms: once we decide to map the first cycle to either itself or the second cycle, in one of $10$ ways, we have $10$ ways to complete the automorphism.
  2. Consider the graph made up of two $5$-cycles with a single edge connecting them. This has only $2$ automorphisms: we can choose to map the first cycle to itself or to the second cycle, but not all automorphisms of the cycle can be completed to an automorphism of the whole graph.
Related Question