Some Pictures of Graphs

Petersen graph Showing automorphism of order 5	Petersen graph Showing automorphism of order 3
Petersen graph Showing automorphism of order 4	Petersen graph Showing automorphism of order 3

My 10-year-old son commented that the fourth picture looks 3-dimensional. (Imagine one vertex as being at the origin, with two vertices along each axis, and six vertices on aplane cutting through the three axes, avoiding the origin.)

---

Coxeter graph Showing automorphism of order 7	Coxeter graph Showing automorphism of order 8
Coxeter graph Showing automorphism of order 6	Coxeter graph Showing automorphism of order 3

For a vertex-transitive graph, such as the Petersen graph or the Coxeter graph, one way to "discover" nice drawings is to look at the automorphism group. Here is the (vertex version of the) cycle index polynomial of the Coxeter graph:

( 84s₈³s₄ + 42s₄⁶s₂² + 48s₇⁴ + 49s₁⁴s₂¹² + 56s₃s₆⁴s₁ + 5 6s₁s₃⁹ + s₁²⁸ ) / 336.
The automorphisms have orders 8,7,6,4,3,2,1.

---

The two graphs with 14 vertices and maximum independent set of cardinality 5
(Verified by computer search: Bajnok and Brinkmann, 1994)

P(7,2)	P(7,3) ≡ P(7,2)
G14,5	G14,5

Exercise: Here are the same two graphs. Which is which?



More general question: Consider the graph H whose vertices are the 3-regular graphs on 2n vertices, with two graphs being adjacent if they differ only in the interchange of a pair of edges, as do P(7,2) and G_14,5. (That is, a switch of a pair of edges in the first graph leaves a graph isomorphic to the second graph.)
What is the diameter of H?

---

The seven (known) connected triangle-free graphs with maximum degree at most three and bipartite density 4/5

C5

Petersen graph ≡ P(5,2)

Dodecahedron ≡ P(10,2)

---

What page of graph pictures would be complete without sketches of the platonic solids?

Dodecahedron ≡ P(10,2)

3-Cube ≡ P(4,1)

Tetrahedron

Icosahedron

Octahedron

---

Office: Room 286, Science & Engineering
Phone: (561) 367-3350
Fax: (561) 367-2436
URL: http://www.math.fau.edu/locke/graphmat.htm