Skip to main content
1 of 3
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

The Petersen graph is a small wonderful and rather exceptional creature. It is not a paradigm.

Vary your construction:

For $G = C_m$, $H = K_2$ and

  • $\pi_1(i) = \text{id}$ for $i=1,\dots,m$
  • $\pi_2(1) = \text{id}$
  • $\pi_2(2) = (12)(3\cdots m)$

I don't think that the result is vertex transitive so your construction need not (and probably seldom) gives a vertex transitive result.

There are many vertex transitive graphs with a prime number of vertices, none of them is a product. So there are graphs which do not arise in this manner.

What can you get? Can you get $K_{2m}$ minus a matching for $m=3$, or even any $m \ge 3$?

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104