Some of the finite structures considered in

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

have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...

, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.

Individual graphs

File:Balaban 10-cage alternative drawing.svg, Balaban 10-cage File:Balaban 11-cage.svg, Balaban 11-cage File:Bidiakis cube.svg,

Bidiakis cube In the mathematical field of graph theory, the bidiakis cube is a 3-regular graph with 12 vertices and 18 edges. Construction The bidiakis cube is a cubic Hamiltonian graph and can be defined by the LCF notation 6,4,-4sup>4. The bidiakis cube ...

File:Brinkmann graph LS.svg, Brinkmann graph File:Bull graph.circo.svg,

Bull graph In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges. It has chromatic number 3, chromatic index 3, radius 2, diameter 3 and ...

File:Butterfly graph.svg,

Butterfly graph In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar, undirected graph with 5 vertices and 6 edges. It can be constructed by joining 2 copies of the cycle graph with a ...

File:Chvatal graph.draw.svg,

Chvátal graph In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal in 1970. It is the smallest graph that is triangle-free, 4-regular, and 4-chromatic. Coloring, d ...

File:Diamond graph.svg,

Diamond graph In the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chromat ...

File:Dürer graph.svg, Dürer graph File:Ellingham-Horton 54-graph.svg, Ellingham–Horton 54-graph File:Ellingham-Horton 78-graph.svg, Ellingham–Horton 78-graph File:Errera graph.svg,

Errera graph In the mathematical field of graph theory, the Errera graph is a graph with 17 vertices and 45 edges. Alfred Errera published it in 1921 as a counterexample to Kempe's erroneous proof of the four color theorem; it was named after Errera by . Pro ...

File:Franklin graph.svg,

Franklin graph In the mathematical field of graph theory, the Franklin graph is a 3-regular graph with 12 vertices and 18 edges. The Franklin graph is named after Philip Franklin, who disproved the Heawood conjecture on the number of colors needed when a two ...

File:Frucht planar Lombardi.svg,

Frucht graph In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939. The Frucht graph is a pancyclic, Halin graph with chromati ...

File:Goldner-Harary graph.svg,

Goldner–Harary graph In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal ...

File:GolombGraph.svg,

Golomb graph In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it (with a non-planar embedding) as a unit distance graph that requires four colors in any graph colori ...

File:Groetzsch-graph.svg,

Grötzsch graph In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in ...

File:Harries graph alternative_drawing.svg, Harries graph File:Harries-wong graph.svg, Harries–Wong graph File:Herschel graph no col.svg,

Herschel graph In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph (the graph of a convex polyhedron), and is the smallest polyhedral graph that does not have a Ha ...

File:Hoffman graph.svg,

Hoffman graph In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q4. The Hoffman graph has many common properti ...

File:Holt graph.svg,

Holt graph In graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter ...

File:Horton graph.svg,

Horton graph In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conject ...

File:Kittell graph.svg,

Kittell graph In the mathematical field of graph theory, the Kittell graph is a planar graph with 23 vertices and 63 edges. Its unique planar embedding has 42 triangular faces. The Kittell graph is named after Irving Kittell, who used it as a counterexample t ...

File:Markström-Graph.svg, Markström graph File:McGee graph.svg,

McGee graph In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges. The McGee graph is the unique (3,7)-cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage tha ...

File:Meredith graph.svg,

Meredith graph In the mathematical field of graph theory, the Meredith graph is a 4- regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973. The Meredith graph is 4- vertex-connected and 4- edge-connected, has chromati ...

File:Moser spindle.svg ,

Moser spindle In graph theory, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit d ...

File:Sousselier graph.svg,

Sousselier graph The Sousselier graph is, in graph theory, a hypohamiltonian graph with 16 vertices and 27 edges. It has book thickness 3 and queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined anal ...

File:Poussin graph planar.svg, Poussin graph File:Robertson graph.svg,

Robertson graph In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4- regular undirected graph with 19 vertices and 38 edges named after Neil Robertson. The Robertson graph is the unique (4,5)-cage graph and was discovered by Rob ...

File:Sylvester graph.svg, Sylvester graph File:Tutte fragment.svg,

Tutte's fragment In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 ed ...

File:Tutte graph.svg,

Tutte graph In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8. The Tutte graph is a cubic polyhedral ...

File:Young-Fibonacci.svg, Young–Fibonacci graph File:Wagner graph ham.svg,

Wagner graph In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph. Properties As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, ...

File:Wells graph.svg,

Wells graph The Wells graph is the unique distance-regular graph with intersection array \. . Its spectrum is 5^1 \sqrt^8 1^10 (-\sqrt)^8(-3)^5. Its queue number is 3 and its upper bound on the book thickness In graph theory, a book embedding is a genera ...

File:Wiener-Araya.svg, Wiener–Araya graph File:Windmill graph Wd(5,4).svg,

Windmill graph In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. Propert ...

Highly symmetric graphs

Strongly regular graphs

The

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have commo ...

on ''v'' vertices and rank ''k'' is usually denoted srg(''v,k'',λ,μ). File:Clebsch graph.svg,

Clebsch graph In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it ...

File:Cameron graph.svg, Cameron graph File:Petersen1 tiny.svg,

File:Hall janko graph.svg,

Hall–Janko graph In the mathematical field of graph theory, the Hall–Janko graph, also known as the Hall-Janko-Wales graph, is a 36- regular undirected graph with 100 vertices and 1800 edges. It is a rank 3 strongly regular graph with parameters (100,36,14,12) ...

File:Hoffman singleton graph circle2.gif,

Hoffman–Singleton graph In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7- regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman an ...

File:Higman Sims Graph.svg,

Higman–Sims graph In mathematical graph theory, the Higman–Sims graph is a 22-regular graph, regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common ...

File:Paley13 no label.svg,

Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, whic ...

of order 13 File:Shrikhande graph symmetrical.svg,

Shrikhande graph In the mathematics, mathematical field of graph theory, the Shrikhande graph is a Gallery of named graphs, named graph discovered by S. S. Shrikhande in 1959.. It is a strongly regular graph with 16 vertex (graph theory), vertices and 48 edge (gra ...

File:Schläfli graph.svg,

Schläfli graph In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16- regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8). ...

File:Brouwer Haemers graph.svg,

Brouwer–Haemers graph In the mathematical field of graph theory, the Brouwer–Haemers graph is a 20- regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construct ...

File:Local mclaughlin graph.svg, Local McLaughlin graph File:Perkel graph embeddings.svg,

Perkel graph In mathematics, the Perkel graph, named after Manley Perkel, is a 6-regular graph with 57 vertices and 171 edges. It is the unique distance-regular graph with intersection array (6, 5, 2; 1, 1, 3).Coolsaet, K. and Degraer, J. "A Computer Assisted ...

File:Gewirtz graph embeddings.svg, Gewirtz graph

Symmetric graphs

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

is one in which there is a symmetry (

graph automorphism In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph is a permutation of the ...

) taking any ordered pair of adjacent vertices to any other ordered pair; the

Foster census In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In ot ...

lists all small symmetric 3-regular graphs. Every strongly regular graph is symmetric, but not vice versa. File:Heawood Graph.svg,

Heawood graph Heawood is a surname. Notable people with the surname include: *Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture **Heawood graph **Heawood number In mathematics, the Heawood number ...

File:Möbius–Kantor unit distance.svg,

Möbius–Kantor graph In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen gra ...

File:Pappus graph.svg,

Pappus graph In the mathematical field of graph theory, the Pappus graph is a bipartite 3- regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek ...

File:DesarguesGraph.svg,

Desargues graph In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level ...

File:Nauru graph.svg,

Nauru graph In the mathematics, mathematical field of graph theory, the Nauru graph is a symmetric graph, symmetric bipartite graph, bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag o ...

File:Coxeter graph.svg,

Coxeter graph In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter. Properties The Coxeter ...

File:Tutte eight cage.svg,

Tutte–Coxeter graph In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. ...

File:Dyck graph.svg,

Dyck graph In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck. It is Hamiltonian with 120 distinct Hamiltonian cycles. It has chromatic number 2, chromatic index 3, radi ...

File:Klein graph.svg,

Klein graph In the mathematics, mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable Surface (topology), surface of Surface (topology)#Classification_of_cl ...

File:Foster graph.svg,

Foster graph In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges. The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is ...

File:Biggs-Smith graph.svg,

Biggs–Smith graph In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges. It has chromatic number 3, chromatic index 3, radius 7, diameter 7 and girth 9. It is also a 3- vertex-connected graph a ...

File:Rado graph.svg, The

Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...

Semi-symmetric graphs

File:Folkman_Lombardi.svg,

Folkman graph Folkman may refer to: People * Jens Christian Folkman Schaanning, a Norwegian politician * Jon Folkman, an American mathematician * Judah Folkman, an American medical scientist * Roy Folkman, an Israeli politician Math * Folkman graph, a type of ...

File:Gray graph hamiltonian.svg,

Gray graph Grey (more common in British English) or gray (more common in American English) is an intermediate color between black and white. It is a neutral or achromatic color, meaning literally that it is "without color", because it can be composed o ...

File:Ljubljana graph hamiltonian.svg,

Ljubljana graph In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges. It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there ...

File:Tutte 12-cage.svg,

Tutte 12-cage In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in 1966. ...

Graph families

Complete graphs

The

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

n

vertices is often called the ''

n

-clique'' and usually denoted

K_n

, from German ''komplett''. File:Complete graph K1.svg,

K_1

File:Complete graph K2.svg,

K_2

File:Complete graph K3.svg,

K_3

File:Complete graph K4.svg,

K_4

File:Complete graph K5.svg,

K_5

File:Complete graph K6.svg,

K_6

File:Complete graph K7.svg,

K_7

File:Complete graph K8.svg,

K_8

Complete bipartite graphs

The

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

is usually denoted

K_

. For

n=1

see the section on star graphs. The graph

K_

equals the 4-cycle

C_4

(the square) introduced below. File:Biclique K 2 3.svg,

K_

File:Biclique K 3 3.svg,

K_

, the

utility graph As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...

File:Biclique K 2 4.svg,

K_

File:Biclique K 3 4.svg,

K_

Cycles

The

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

n

vertices is called the ''n-cycle'' and usually denoted

C_n

. It is also called a ''cyclic graph'', a ''polygon'' or the ''n-gon''. Special cases are the ''triangle''

C_3

, the ''square''

C_4

, and then several with Greek naming ''pentagon''

C_5

, ''hexagon''

C_6

, etc. File:Complete graph K3.svg,

C_3

File:Circle graph C4.svg,

C_4

File:Circle graph C5.svg,

C_5

File:Undirected 6 cycle.svg,

C_6

Friendship graphs

The

friendship graph In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or -fan) is a planar, undirected graph with vertices and edges. The friendship graph can be constructed by joining copies of the cycle graph with a ...

''F_n'' can be constructed by joining ''n'' copies of the

''C''₃ with a common vertex. Friendship graphs

Fullerene graphs

In graph theory, the term

fullerene A fullerene is an allotrope of carbon whose molecule consists of carbon atoms connected by single and double bonds so as to form a closed or partially closed mesh, with fused rings of five to seven atoms. The molecule may be a hollow sphere, ...

refers to any 3- regular,

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

with all faces of size 5 or 6 (including the external face). It follows from

Euler's polyhedron formula In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's ...

, ''V'' – ''E'' + ''F'' = 2 (where ''V'', ''E'', ''F'' indicate the number of vertices, edges, and faces), that there are exactly 12 pentagons in a fullerene and ''h'' = ''V''/2 – 10 hexagons. Therefore ''V'' = 20 + 2''h''; ''E'' = 30 + 3''h''. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds. File:Graph of 20-fullerene w-nodes.svg, 20-fullerene (

dodecahedral In geometry, a dodecahedron (Greek , from ''dōdeka'' "twelve" + ''hédra'' "base", "seat" or "face") or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagon ...

graph) File:Graph of 24-fullerene w-nodes.svg, 24-fullerene (

Hexagonal truncated trapezohedron In geometry, the truncated hexagonal trapezohedron is the fourth in an infinite series of truncated trapezohedra. It has 12 pentagon and 2 hexagon faces. It can be constructed by taking a hexagonal trapezohedron and truncating the polar axis v ...

graph) File:Graph of 26-fullerene 5-base w-nodes.svg, 26-fullerene graph File:Graph of 60-fullerene w-nodes.svg, 60-fullerene ( truncated icosahedral graph) File:Graph of 70-fullerene w-nodes.svg, 70-fullerene An algorithm to generate all the non-isomorphic fullerenes with a given number of hexagonal faces has been developed by G. Brinkmann and A. Dress. G. Brinkmann also provided a freely available implementation, calle
fullgen

Platonic solids

The

on four vertices forms the skeleton of the

tetrahedron In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...

, and more generally the complete graphs form skeletons of

simplices In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...

. The

hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, ...

s are also skeletons of higher-dimensional regular

polytope In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...

s. File:3-cube column graph.svg,

Cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

n=8

m=12

File:Octahedral graph.circo.svg,

Octahedron In geometry, an octahedron (plural: octahedra, octahedrons) is a polyhedron with eight faces. The term is most commonly used to refer to the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at ea ...

n=6

m=12

File:Dodecahedral graph.neato.svg,

Dodecahedron In geometry, a dodecahedron (Greek , from ''dōdeka'' "twelve" + ''hédra'' "base", "seat" or "face") or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagon ...

n=20

m=30

File:Icosahedron graph.svg,

Icosahedron In geometry, an icosahedron ( or ) is a polyhedron with 20 faces. The name comes and . The plural can be either "icosahedra" () or "icosahedrons". There are infinitely many non- similar shapes of icosahedra, some of them being more symmetrica ...

n=12

m=30

Truncated solids

File:3-simplex_t01.svg,

Truncated tetrahedron In geometry, the truncated tetrahedron is an Archimedean solid. It has 4 regular hexagonal faces, 4 equilateral triangle faces, 12 vertices and 18 edges (of two types). It can be constructed by truncating all 4 vertices of a regular tetrahedro ...

File:Truncated cubical graph.neato.svg,

Truncated cube In geometry, the truncated cube, or truncated hexahedron, is an Archimedean solid. It has 14 regular faces (6 octagonal and 8 triangular), 36 edges, and 24 vertices. If the truncated cube has unit edge length, its dual triakis octahedron has edg ...

File:Truncated octahedral graph.neato.svg,

Truncated octahedron In geometry, the truncated octahedron is the Archimedean solid that arises from a regular octahedron by removing six pyramids, one at each of the octahedron's vertices. The truncated octahedron has 14 faces (8 regular hexagon, hexagons and 6 Squa ...

File:Truncated Dodecahedral Graph.svg,

Truncated dodecahedron In geometry, the truncated dodecahedron is an Archimedean solid. It has 12 regular decagonal faces, 20 regular triangular faces, 60 vertices and 90 edges. Geometric relations This polyhedron can be formed from a regular dodecahedron by truncat ...

File:Icosahedron t01 H3.png,

Truncated icosahedron In geometry, the truncated icosahedron is an Archimedean solid, one of 13 convex isogonal nonprismatic solids whose 32 faces are two or more types of regular polygons. It is the only one of these shapes that does not contain triangles or squares. ...

Snarks

snark Snark may refer to: Fictional creatures * Snark (Lewis Carroll), a fictional animal species in Lewis Carroll's ''The Hunting of the Snark'' (1876) * Zn'rx, a race of fictional aliens in Marvel Comics publications, commonly referred to as "Snark ...

is a bridgeless

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

that requires four colors in any proper

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

. The smallest snark is the

, already listed above. File:First Blanusa snark.svg, Blanuša snark (first) File:Second Blanusa snark.svg, Blanuša snark (second) File:Double-star snark.svg, Double-star snark File:Flower snarkv.svg,

Flower snark In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975. As snarks, the flower snarks are connected, bridgeless cubic graphs with chromatic index equal to 4. The flower ...

File:Loupekine 1.svg, Loupekine snark (first) File:Loupekine 2.svg, Loupekine snark (second) File:Szekeres-snark.svg, Szekeres snark File:Tietze's graph.svg, Tietze graph File:Watkins snark.svg, Watkins snark

Star

star A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...

''S''_''k'' is the

''K''_1,''k''. The star ''S''₃ is called the claw graph. Star graphs

Wheel graphs

The

wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...

''W_n'' is a graph on ''n'' vertices constructed by connecting a single vertex to every vertex in an (''n'' − 1)-cycle. Wheel graphs

References

{{DEFAULTSORT:Gallery Of Named Graphs Named Graphs * Image galleries