This partial list of

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

s contains definitions of graphs and graph families. For collected definitions 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 ...

terms that do not refer to individual graph types, such as ''vertex'' and ''path'', see

Glossary of graph theory This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

. For links to existing articles about particular kinds of graphs, see Graphs. Some of the finite structures considered in

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

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

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

Butterfly graph In the mathematics, mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar graph, planar, undirected graph with 5 Vertex (graph theory), vertices and 6 edges. It can be construct ...

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

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

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 mathematics, mathematical field of graph theory, the Errera graph is a graph with 17 vertex (graph theory), vertices and 45 edge (graph theory), edges. Alfred Errera published it in 1921 as a counterexample to Alfred Kempe, Kempe's erroneous ...

File:Franklin graph.svg,

Franklin graph Franklin may refer to: People and characters * Franklin (given name), including list of people and characters with the name * Franklin (surname), including list of people and characters with the name * Franklin (class), a member of a historica ...

File:Frucht planar Lombardi.svg,

Frucht graph In the mathematics, mathematical field of graph theory, the Frucht graph is a cubic graph with 12 Vertex (graph theory), vertices, 18 edges, and no nontrivial graph automorphism, symmetries. It was first described by Robert Frucht in 1949. The F ...

File:Goldner-Harary graph.svg,

Goldner–Harary graph In the mathematics, mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after Anita M. Goldner and Frank Harary, who proved in 1975 that it was the smallest Hamilt ...

File:GolombGraph.svg,

Golomb graph In graph theory, the Golomb graph is a polyhedral graph with 10 vertex (graph theory), vertices and 18 edge (graph theory), edges. It is named after Solomon W. Golomb, who constructed it (with a non-planar graph, planar embedding) as a unit distan ...

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

File:Harries graph alternative_drawing.svg,

Harries graph In the mathematical field of graph theory, the Harries graph or Harries (3-10)-cage is a 3-regular, undirected graph with 70 vertices and 105 edges. The Harries graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 an ...

File:Harries-wong graph.svg,

Harries–Wong graph In the mathematical field of graph theory, the Harries–Wong graph is a 3-regular undirected graph with 70 vertices and 105 edges. The Harries–Wong graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 and is H ...

File:Herschel graph no col.svg,

Herschel graph In graph theory, a branch of mathematics, the Herschel graph is a bipartite graph, 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 d ...

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 mathematics, 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 graph, cage (the smallest cubic graph of girth 7). It is also t ...

File:Meredith graph.svg, Meredith graph 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 can be dra ...

File:Sousselier graph.svg, Sousselier graph 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 The Sylvester graph is the unique distance-regular graph with intersection array \. It is a subgraph of the Hoffman–Singleton graph In the mathematical field of graph theory, the Hoffman–Singleton graph is a undirected graph with 50 ve ...

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

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

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^ (-\sqrt)^8(-3)^5. Its queue number is 3 and an upper bound on its book thickness In graph theory, a book embedding is a generaliza ...

File:Wiener-Araya.svg,

Wiener–Araya graph The Wiener–Araya graph is, in graph theory, a graph on 42 vertices with 67 edges. It is hypohamiltonian, which means that it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian Ha ...

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 a regular graph with vertices and degree such that for some given integers \lambda, \mu \ge 0 * every two adjacent vertices have common neighbours, and * every two non-adjacent vertices h ...

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

Clebsch graph In the mathematics, mathematical field of graph theory, the Clebsch graph is either of two complement (graph theory), 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 ...

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

File:Hall janko graph.svg, Hall–Janko graph File:Hoffman singleton graph circle2.gif,

Hoffman–Singleton graph In the mathematical field of graph theory, the Hoffman–Singleton graph is a 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 and Robert ...

File:Higman Sims Graph.svg,

Higman–Sims graph In mathematical graph theory, the Higman–Sims graph is a 22- 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 neighbor an ...

File:Paley13 no label.svg,

Paley graph In mathematics, Paley graphs are 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, which yiel ...

of order 13 File:Shrikhande graph symmetrical.svg,

Shrikhande graph In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959.. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has ...

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

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

Gewirtz graph The Gewirtz graph is a strongly regular graph with 56 vertices and valency 10. It is named after the mathematician Allan Gewirtz, who described the graph in his dissertation.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 ...

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

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

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

Heawood graph In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood. Combinatorial properties The graph is cubic, and all cycles in the graph have six or more edges. ...

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

Möbius–Kantor graph In the mathematics, mathematical field of graph theory, the Möbius–Kantor graph is a symmetric graph, symmetric bipartite graph, bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It ...

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

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 mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru. It has chromatic number 2, chro ...

File:Coxeter graph.svg,

Coxeter graph In the mathematics, 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 graph, cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter ...

File:Tutte eight cage.svg,

Tutte–Coxeter graph In the mathematics, 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 (graph theory), girt ...

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

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 mathematics, mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a Countable set, countably infinite graph that can be constructed (with probability one) by choosing independently at random for eac ...

Semi-symmetric graphs

File:Folkman_Lombardi.svg,

Folkman graph In the mathematical field of graph theory, the Folkman graph is a 4- regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not ...

File:Gray graph hamiltonian.svg,

Gray graph In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), t ...

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, rediscovered in 2002 and named after Ljubljana (the capital of Slovenia). Conder, M.; Malnič, A.; Marušič, D.; Pi ...

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. It is named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in ...

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

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 In economics, utility is a measure of a certain person's satisfaction from a certain state of the world. Over time, the term has been used with at least two meanings. * In a normative context, utility refers to a goal or objective that we wish ...

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, a

fullerene A fullerene is an allotropes of carbon, allotrope of carbon whose molecules consist 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 six atoms. The molecules may ...

is any

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...

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

, ''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 (; ) or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagons as faces, which is a Platonic solid. There are also three regular s ...

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 Truncation (geometry), truncat ...

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 (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...

, 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 cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has ...

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

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

Cube A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...

n=8

m=12

File:Octahedral graph.circo.svg,

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

n=6

m=12

File:Dodecahedral graph.neato.svg,

Dodecahedron In geometry, a dodecahedron (; ) or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagons as faces, which is a Platonic solid. There are also three Kepler–Po ...

n=20

m=30

File:Icosahedron graph.svg,

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

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 truncation (geometry), truncating all 4 vertices of ...

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 triangle (geometry), triangular), 36 edges, and 24 vertices. If the truncated cube has unit edge length, its dual triak ...

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. Construction The truncated dodecahedron is constructed from a regular dodecahedron by cu ...

File:Icosahedron t01 H3.png,

Truncated icosahedron In geometry, the truncated icosahedron is a polyhedron that can be constructed by Truncation (geometry), truncating all of the regular icosahedron's vertices. Intuitively, it may be regarded as Ball (association football), footballs (or soccer ...

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

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

that requires four colors in any proper

edge coloring In graph theory, a proper 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 ...

. 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 In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges. It was the fifth known snark, discovered by George Szekeres in 1973. As a snark, the Szekeres graph is a connected, bridgeless cubic graph wi ...

File:Tietze's graph.svg, Tietze graph File:Watkins snark.svg, Watkins snark

Star

star A star is a luminous spheroid of plasma (physics), plasma held together by Self-gravitation, self-gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night sk ...

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

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

Wheel graphs

The

wheel graph In graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with vertices can also be defined as the 1-skeleton of an pyramid. Some authors write to denote a wheel graph ...

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

Other graphs

This partial list contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own.

Gear

A gear graph, denoted ''G''_''n'', is a graph obtained by inserting an extra vertex between each pair of adjacent vertices on the perimeter of a

''W''_''n''. Thus, ''G''_''n'' has 2''n''+1 vertices and 3''n'' edges. Gear graphs are examples of

squaregraph In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unboun ...

s, and play a key role in the

forbidden graph characterization In graph theory, a branch of mathematics, many important families of Graph (discrete mathematics), graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family whic ...

of squaregraphs. Gear graphs are also known as cogwheels and bipartite wheels.

Helm

A helm graph, denoted ''H_n'', is a graph obtained by attaching a single edge and node to each node of the outer circuit of a

''W_n''.

Lobster

A lobster graph is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

in which all the vertices are within distance 2 of a central

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desir ...

. Compare ''caterpillar''.

Web

The web graph ''W''_''n'',''r'' is a graph consisting of ''r'' concentric copies of the

''C''_''n'', with corresponding vertices connected by "spokes". Thus ''W''_''n'',1 is the same graph as ''C''_''n'', and ''W''_n,2 is a

prism PRISM is a code name for a program under which the United States National Security Agency (NSA) collects internet communications from various U.S. internet companies. The program is also known by the SIGAD . PRISM collects stored internet ...

. A web graph has also been defined as a prism graph ''Y''_{''n''+1, 3}, with the edges of the outer cycle removed.

References

{{DEFAULTSORT:Graphs Mathematics-related lists * *