In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the Folkman graph is a 4- regular graph with 20 vertices and 40 edges. It is a regular

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

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 In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edg ...

. It is named after Jon Folkman, who constructed it for this property in 1967. The Folkman graph can be constructed either using

modular arithmetic In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...

or as the subdivided double of the five-vertex

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

. Beyond the investigation of its symmetry, it has also been investigated as a

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a c ...

for certain questions of

graph embedding In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of ,1/math>) ...

Construction

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 Frank Harary (March 11, 1921 – January 4, 2005) was an American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory. Harary was a master of clear exposition and, together with ...

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

, based on a prime number

p

congruent to 1 mod 4. For each such prime, there is a number

r

such that

r^2=-1

mod

p

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

2pr

vertices. The Folkman graph is the result of this construction for

p=5

and

r=2

Another construction for the Folkman graph begins with the

on five vertices,

K_5

. A new vertex is placed on each of the ten edges of

K_5

, subdividing each edge into a two-edge path. Then, each of the five original vertices of

K_5

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

K_5

form the other side of the bipartition. Because each edge of the result comes from a doubled half of an edge of

K_5

, and because

K_5

has symmetries taking every half-edge to every other half-edge, the result is edge-transitive. It is not vertex-transitive, because the subdivision vertices are not twins with any other vertex, making them different from the doubled vertices coming 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 In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

such as

K_5

or the graph of the

octahedron In geometry, an octahedron (: octahedra or octahedrons) is any polyhedron with eight faces. One special case is the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex. Many types of i ...

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

Algebraic properties

The

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

of the Folkman graph (its group of symmetries) combines the

5!

symmetries of

K_5

with the

2^5

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

5!\cdot 2^5=3840

symmetries. 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 In geometry, a polytope (for example, a polygon or a polyhedron) or a Tessellation, tiling is isotoxal () or edge-transitive if its Symmetry, symmetries act Transitive group action, transitively on its Edge (geometry), edges. Informally, this mea ...

and regular, but not

vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face i ...

. Such graphs are called

s and were first studied by Folkman in 1967 who discovered the graph on 20 vertices that now is named after him. Like all semi-symmetric graphs, the Folkman graph is bipartite. 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

K_5

, but imprimitively on the vertices constructed by doubling the vertices of

K_5

. 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. The

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the Folkman graph is

(x-4) x^ (x+4) (x^2-6)^4

Other properties

The Folkman graph has a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

, and more strongly a

Hamiltonian decomposition In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed grap ...

into two Hamiltonian cycles. Like every bipartite graph, its

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

is two, and its

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

(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, 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. Its radius is 3 and its diameter is 4. If

v

is one of the doubled vertices of the

K_5

construction, then all other vertices are at most three steps away from

v

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

K_5

) that are four steps apart from each other. Because the graph contains many 4-cycles, its

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

is 4, the minimum possible for a bipartite graph. It is also 4- vertex-connected and 4- edge-connected. Its

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests ...

and

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of ...

are both 5. The Folkman graph has

genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...

3: it can be embedded on a triple torus, but not on any simpler oriented surface. It has

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on ...

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 graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...

s need only a number of pages equal to their degree.

References

{{reflist, refs= {{citation , last1 = Alam , first1 = Jawaherul Md. , last2 = Bekos , first2 = Michael A. , last3 = Dujmović , first3 = Vida , author3-link = Vida Dujmović , last4 = Gronemann , first4 = Martin , last5 = Kaufmann , first5 = Michael , last6 = Pupyrev , first6 = Sergey , arxiv = 1803.10030 , doi = 10.1016/j.tcs.2021.01.035 , journal =

Theoretical Computer Science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, mr = 4221556 , pages = 1–22 , title = On dispersable book embeddings , volume = 861 , year = 2021 {{citation , last = Brinkmann , first = Gunnar , arxiv = 2005.08243 , doi = 10.26493/1855-3974.2320.c2d , issue = 4 , journal = Ars Mathematica Contemporanea , mr = 4498572 , at = Paper No. 1 , title = A practical algorithm for the computation of the genus , url = https://amc-journal.eu/index.php/amc/article/view/2320 , volume = 22 , year = 2022, s2cid = 218674244 {{citation , last1 = Boesch , first1 = F. , last2 = Tindell , first2 = R. , doi = 10.1002/jgt.3190080406 , issue = 4 , journal = Journal of Graph Theory , mr = 766498 , pages = 487–499 , title = Circulants and their connectivities , volume = 8 , year = 1984 {{citation , last1 = Conder , first1 = Marston , author1-link = Marston Conder , last2 = Stokes , first2 = Klara , doi = 10.26493/1855-3974.1800.40c , issue = 1 , journal = Ars Mathematica Contemporanea , mr = 3992757 , pages = 1–35 , title = New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces , url = https://amc-journal.eu/index.php/amc/article/view/1800 , volume = 17 , year = 2019, doi-access = free , hdl = 2292/57926 , hdl-access = free {{citation , first = J. , last = Folkman , authorlink=Jon Folkman , title = Regular line-symmetric graphs , journal = Journal of Combinatorial Theory , volume =3 , year = 1967 , issue = 3 , pages = 215–232 , doi = 10.1016/S0021-9800(67)80069-3, doi-access = free {{citation , last = Galvin , first = Fred , author-link = Fred Galvin , doi = 10.1006/jctb.1995.1011 , issue = 1 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...

, mr = 1309363 , pages = 153–158 , series = Series B , title = The list chromatic index of a bipartite multigraph , volume = 63 , year = 1995, doi-access = free {{citation , last1 = Heule , first1 = Marijn , last2 = Szeider , first2 = Stefan , doi = 10.1145/2736696 , issue = 3 , journal = ACM Transactions on Computational Logic , pages = 24:1–24:27 , title = A SAT approach to clique-width , volume = 16 , year = 2015, arxiv = 1304.5498 {{MathWorld, id=FolkmanGraph, title=Folkman Graph, mode=cs2 {{citation , last1 = Potočnik , first1 = Primož , last2 = Wilson , first2 = Steve , doi = 10.1016/j.jctb.2006.03.007 , issue = 2 , journal =

, mr = 2290322 , pages = 217–236 , series = Series B , title = Tetravalent edge-transitive graphs of girth at most 4 , volume = 97 , year = 2007, doi-access = free {{citation , last1 = Potočnik , first1 = Primož , last2 = Wilson , first2 = Stephen E. , doi = 10.26493/1855-3974.311.4a8 , issue = 2 , journal = Ars Mathematica Contemporanea , mr = 3240442 , pages = 341–352 , title = Linking rings structures and tetravalent semisymmetric graphs , volume = 7 , year = 2014, doi-access = free {{citation , last = Skiena , first = Steven , author-link = Steven Skiena , location = Reading, Massachusetts , pages = 186–187 , publisher = Addison-Wesley , title = Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica , year = 1990 {{citation , last = Ziv-Av , first = Matan , pages = 24–25 , publisher = Ben-Gurion University , title = Interactions between Coherent Configurations and Some Classes of Objects in Extremal Combinatorics , type = Doctoral thesis , url = https://aranne5.bgu.ac.il/others/Ziv-AvMatan3.pdf , year = 2013 Individual graphs Regular graphs