It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph.

[1] It is named after Jon Folkman, who constructed it for this property in 1967.

[2] The Folkman graph can be constructed either using modular arithmetic or as the subdivided double of the five-vertex complete graph.

Semi-symmetric graphs are defined as regular graphs (that is, graphs in which all vertices touch equally many edges) in which each two edges are symmetric to each other, but some two vertices are not symmetric.

Jon Folkman was inspired to define and research these graphs in a 1967 paper, after seeing an unpublished manuscript by E. Dauber and Frank Harary which gave examples of graphs meeting the symmetry condition but not the regularity condition.

Folkman's original construction of this graph was a special case of a more general construction of semi-symmetric graphs using modular arithmetic, based on a prime number

, and Folkman uses modular arithmetic to construct a semi-symmetric graph with

The Folkman graph is the result of this construction for

, subdividing each edge into a two-edge path.

is doubled, replacing it by two vertices with the same neighbors.

The ten subdivision vertices form one side of the bipartition of the Folkman graph, and the ten vertices in twin pairs coming from the doubled vertices of

It is not vertex-transitive, because the subdivision vertices are not twins with any other vertex, making them different from the doubled vertices coming from

[3] Every 4-regular semi-symmetric graph in which some two vertices have the same neighborhood can be constructed in the same way, by subdividing and then doubling a 4-regular symmetric graph such as

However, there also exist larger 4-regular semi-symmetric graphs that do not have any twin vertices.

ways of swapping some pairs of doubled vertices, for a total of

This group acts transitively on the Folkman graph's edges (it includes a symmetry taking any edge to any other edge) but not on its vertices.

The Folkman graph is the smallest undirected graph that is edge-transitive and regular, but not vertex-transitive.

Its automorphism group includes symmetries taking any vertex to any other vertex that is on the same side of the bipartition, but none that take a vertex to the other side of the bipartition.

Although one can argue directly that the Folkman graph is not vertex-transitive, this can also be explained group-theoretically: its symmetries act primitively on the vertices constructed as subdivision points of

Every symmetry maps a doubled pair of vertices to another doubled pair of vertices, but there is no grouping of the subdivision vertices that is preserved by the symmetries.

[7] The characteristic polynomial of the Folkman graph is

Like every bipartite graph, its chromatic number is two, and its chromatic index (the minimum number of colors needed to color its edges so that no two edges of the same color meet at a vertex) equals its maximum degree,[9] which in this case is four.

For instance, such a coloring can be obtained by using two colors in alternation for each cycle of a Hamiltonian decomposition.

However, there are pairs of subdivision vertices from the construction (coming from disjoint edges of

[10] The Folkman graph has genus 3: it can be embedded on a triple torus, but not on any simpler oriented surface.

[11][12] It has book thickness 3, but requires five pages for a "dispersable" book embedding in which each page is a matching, disproving a conjecture of Frank Bernhart and Paul Kainen that dispersable book embeddings of regular graphs need only a number of pages equal to their degree.