In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Franklin graph is a 3-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegre ...

with 12 vertices and 18 edges. The Franklin graph is named after

Philip Franklin Philip Franklin (October 5, 1898 – January 27, 1965) was an American mathematician and professor whose work was primarily focused in analysis. Dr. Franklin received a B.S. in 1918 from City College of New York (who later awarded him ...

, who disproved the

Heawood conjecture In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required ...

on the number of colors needed when a two-dimensional surface is partitioned into cells by a

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

.Franklin, P. "A Six Color Problem." J. Math. Phys. 13, 363-379, 1934. The Heawood conjecture implied that the maximum chromatic number of a map on the

Klein bottle In topology, a branch of mathematics, the Klein bottle () is an example of a non-orientable surface; it is a two-dimensional manifold against which a system for determining a normal vector cannot be consistently defined. Informally, it is a ...

should be seven, but Franklin proved that in this case six colors always suffice. (The Klein bottle is the only surface for which the Heawood conjecture fails.) The Franklin graph can be embedded in the Klein bottle so that it forms a map requiring six colors, showing that six colors are sometimes necessary in this case. This embedding is the

Petrie dual In topological graph theory, the Petrie dual of an embedded graph (on a 2-manifold with all faces disks) is another embedded graph that has the Petrie polygons of the first embedding as its faces. The Petrie dual is also called the Petrial, and t ...

of its embedding in the

projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...

shown below. It is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

and has

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

chromatic index In graph theory, an edge coloring of a 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 coloring of a graph by the colors red, blue ...

3, radius 3, diameter 3 and

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

4. It is also a 3- vertex-connected and 3- edge-connected

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

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

of the Franklin graph is of order 48 and is isomorphic to Z/2Z×''S''₄, the

direct product In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...

of the

cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bi ...

Z/2Z and the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...

''S''₄. It acts transitively on the vertices of the graph, making it

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

. 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 Franklin graph is :

(x-3) (x-1)^3 (x+1)^3 (x+3) (x^2-3)^2.\

Gallery

Image: Franklin graph 2COL.svg , The

of the Franklin graph is 2. Image: Franklin graph 3color edge.svg, The

of the Franklin graph is 3. Image:franklin_graph.svg, Alternative drawing of the Franklin graph. Image:Franklin graph in projective plane.svg, The Franklin graph embedded in the projective plane as the truncated

hemi-octahedron A hemi-octahedron is an abstract regular polyhedron, containing half the faces of a regular octahedron. It has 4 triangular faces, 6 edges, and 3 vertices. Its dual polyhedron is the hemicube. It can be realized as a projective polyhedron (a ...

References

{{DEFAULTSORT:Franklin Graph Individual graphs Regular graphs