Folkman graph

Folkman graph
Drawing following Folkman (1967), Figure 1
Named afterJon Folkman
Vertices20
Edges40
Radius3
Diameter4
Girth4
Automorphisms5! ยท 25 = 3840
Chromatic number2
Chromatic index4
Genus3
Book thickness3
Queue number2
Properties
Table of graphs and parameters

In the mathematical field of graph theory, the Folkman graph is a graph with 20 vertices and 40 edges. It is quartic (four edges meet at each vertex), and bipartite (its vertices can be divided into two subsets with each edge crossing from one subset to the other). It has symmetries taking every edge to every other edge, but not taking every vertex to every other vertex, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.

The Folkman graph can be constructed either using modular arithmetic or as the subdivided double of the five-vertex complete graph. Beyond the investigation of its symmetry, it has also been used to construct isospectral graphs and investigated as a counterexample for certain questions of graph embedding.