1.
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 each other, such a drawing is called a plane graph or planar embedding of the graph. Every graph that can be drawn on a plane can be drawn on the sphere as well, plane graphs can be encoded by combinatorial maps. The equivalence class of topologically equivalent drawings on the sphere is called a planar map, although a plane graph has an external or unbounded face, none of the faces of a planar map have a particular status. Planar graphs generalize to graphs drawable on a surface of a given genus, in this terminology, planar graphs have graph genus 0, since the plane are surfaces of genus 0. See graph embedding for other related topics, a subdivision of a graph results from inserting vertices into edges zero or more times. Instead of considering subdivisions, Wagners theorem deals with minors, A finite graph is planar if, klaus Wagner asked more generally whether any minor-closed class of graphs is determined by a finite set of forbidden minors. This is now the Robertson–Seymour theorem, proved in a series of papers. In the language of this theorem, K5 and K3,3 are the forbidden minors for the class of planar graphs. In practice, it is difficult to use Kuratowskis criterion to decide whether a given graph is planar. However, there exist fast algorithms for this problem, for a graph with n vertices, for a simple, connected, planar graph with v vertices and e edges, the following simple conditions hold, Theorem 1. If v ≥3 then e ≤ 3v −6, Theorem 2, if v ≥3 and there are no cycles of length 3, then e ≤ 2v −4. In this sense, planar graphs are graphs, in that they have only O edges. The graph K3,3, for example, has 6 vertices,9 edges, therefore, by Theorem 2, it cannot be planar. Note that these theorems provide necessary conditions for planarity that are not sufficient conditions, if both theorem 1 and 2 fail, other methods may be used. As an illustration, in the graph given above, v =5, e =6 and f =3. If the second graph is redrawn without edge intersections, it has v =4, e =6 and f =4. In general, if the property holds for all graphs of f faces

2.
1-planar graph
–
1-planar graphs were first studied by Ringel, who showed that they can be colored with at most seven colors. Later, the number of colors needed to color these graphs. The example of the complete graph K6, which is 1-planar, however, the proof that six colors are always enough is more complicated. This can obviously be done using eight colors by applying the four color theorem to the graph and its dual graph separately. A vertex coloring of the graph corresponds to a vertex-face coloring of the original planar graph. This auxiliary graph is 1-planar, from which it follows that Ringels vertex-face coloring problem may also be solved with six colors, every 1-planar graph with n vertices has at most 4n −8 edges. However, unlike planar graphs, there exist maximal 1-planar graphs that have fewer than 4n −8 edges. A 1-planar graph is said to be an optimal 1-planar graph if it has exactly 4n −8 edges, in a 1-planar embedding of an optimal 1-planar graph, the uncrossed edges necessarily form a quadrangulation. Every quadrangulation gives rise to an optimal 1-planar graph in this way and it follows that every optimal 1-planar graph is Eulerian, that the minimum degree in such a graph is six, and that every optimal 1-planar graph has at least eight vertices of degree exactly six. Additionally, every optimal 1-planar graph is 4-vertex-connected, and every 4-vertex cut in such a graph is a cycle in the underlying quadrangulation. The graphs that have straight 1-planar drawings have a tighter bound of 4n −9 on the maximum number of edges. A complete classification of the 1-planar complete graphs, complete bipartite graphs, every complete bipartite graph of the form K2, n is 1-planar, as is every complete tripartite graph of the form K1,1, n. Other than these infinite sets of examples, the only complete multipartite 1-planar graphs are K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2, and their subgraphs. The minimal non-1-planar complete multipartite graphs are K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. For instance, the bipartite graph K3,6 is 1-planar because it is a subgraph of K1,1,1,6. It is NP-complete to test whether a graph is 1-planar. The problem is tractable when parameterized by cyclomatic number or by tree-depth. In contrast to Fárys theorem for graphs, not every 1-planar graph may be drawn 1-planarly with straight line segments for its edges

3.
Antiprism graph
–
In the mathematical field of graph theory, an antiprism graph is a graph that has one of the antiprisms as its skeleton. An n-sided antiprism has 2n vertices and 4n edges and they are regular, polyhedral, and also Hamiltonian graphs. The first graph in the sequence, the graph, has 6 vertices and 12 edges. Although geometrically the star polygons also form the faces of a different sequence of antiprisms, an antiprism graph is a special case of a circulant graph, Ci2n. Other infinite sequences of polyhedral graph formed in a way from polyhedra with regular-polygon bases include the prism graphs. Other vertex-transitive polyhedral graphs include the Archimedean graphs

4.
Apex graph
–
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph and it is an apex, not the apex because an apex graph may have more than one apex, for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex, the null graph is also counted as an apex graph even though it has no vertex to remove. Apex graphs are closed under the operation of taking minors, contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if G is a graph with apex v, then any contraction or removal that does not involve v preserves the planarity of the remaining graph. If an edge incident to v is contracted, the effect on the graph is equivalent to the removal of the other endpoint of the edge. And if v itself is removed, any vertex may be chosen as the apex. By the Robertson–Seymour theorem, because they form a family of graphs. There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor and these graphs are forbidden minors for the property of being an apex graph. Any other graph G is a graph if and only if none of the forbidden minors is a minor of G. These forbidden minors include the seven graphs of the Petersen family, however, a complete description of them remains unknown. Despite the complete set of forbidden minors remaining unknown, it is possible to test whether a graph is an apex graph. If k is variable, however, the problem is NP-complete, every apex graph has chromatic number at most five, the underlying planar graph requires at most four colors by the four color theorem, and the remaining vertex needs at most one additional color. Jørgensen conjectured that every 6-vertex-connected graph that does not have K6 as a minor must be an apex graph, if this were proved, the Robertson–Seymour–Thomas result on the Hadwiger conjecture would be an immediate consequence. However, if false, it has finitely many counterexamples. A minor-closed family of graphs that has a graph as one of its forbidden minors is known as apex-minor-free. Apex-minor-free graph families obey a strengthened version of the structure theorem, leading to additional approximation algorithms for graph coloring. However, some of results can also be extended to arbitrary minor-closed graph families via structure theorems relating them to apex-minor-free graphs

5.
Apollonian network
–
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar graphs, the uniquely 4-colorable planar graphs. They are named after Apollonius of Perga, who studied a related circle-packing construction, in this way, the triangle containing the new vertex is subdivided into three smaller triangles, which may in turn be subdivided in the same way. The complete graphs on three and four vertices, K3 and K4, are both Apollonian networks, K3 is formed by starting with a triangle and not performing any subdivisions, while K4 is formed by making a single subdivision before stopping. The Goldner–Harary graph is an Apollonian network that forms the smallest non-Hamiltonian maximal planar graph, another more complicated Apollonian network was used by Nishizeki to provide an example of a 1-tough non-Hamiltonian maximal planar graph. As well as being defined by recursive subdivision of triangles, the Apollonian networks have several other equivalent mathematical characterizations and they are the chordal maximal planar graphs, the chordal polyhedral graphs, and the planar 3-trees. They are the uniquely 4-colorable planar graphs, and the graphs with a unique Schnyder wood decomposition into three trees. They are the planar graphs with treewidth three, a class of graphs that can be characterized by their forbidden minors or by their reducability under Y-Δ transforms. They are the planar graphs with degeneracy three. This forms an alternative characterization of the Apollonian networks, they are exactly the maximal planar graphs or equivalently the chordal polyhedral graphs. In an Apollonian network, every clique is a complete graph on four vertices, formed by choosing any vertex. Every minimal clique separator is one of the subdivided triangles, a chordal graph in which all maximal cliques and all minimal clique separators have the same size is a k-tree, and Apollonian networks are examples of 3-trees. Not every 3-tree is planar, but the planar 3-trees are exactly the Apollonian networks, every Apollonian network is also a uniquely 4-colorable graph. It is more difficult to prove, but also true, that every uniquely 4-colorable planar graph is an Apollonian network, therefore, Apollonian networks may also be characterized as the uniquely 4-colorable planar graphs. Apollonian networks also provide examples of planar graphs having as few k-colorings as possible for k >4, however, the planar partial 3-trees, subgraphs of Apollonian networks, are minor-closed. Therefore, according to the Robertson–Seymour theorem, they can be characterized by a number of forbidden minors. The Apollonian graphs are the graphs that do not have any of these four graphs as a minor. In every subgraph of an Apollonian network, the most recently added vertex has degree at most three, so Apollonian networks have degeneracy three

6.
Bidiakis cube
–
In the mathematical field of graph theory, the Bidiakis cube is a 3-regular graph with 12 vertices and 18 edges. The Bidiakis cube is a cubic Hamiltonian graph and can be defined by the LCF notation 4, the Bidiakis cube can also be constructed from a cube by adding edges across the top and bottom faces which connect the centres of opposite sides of the faces. The two additional edges need to be perpendicular to each other, with this construction, the Bidiakis cube is a polyhedral graph, and can be realized as a convex polyhedron. Therefore, by Steinitzs theorem, it is a 3-vertex-connected simple planar graph, the characteristic polynomial of the Bidiakis cube is 2

7.
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 it is also a block graph, a split graph, an interval graph, a claw-free graph, a 1-vertex-connected graph and a 1-edge-connected graph. A graph is bull-free if it has no bull as an induced subgraph, the triangle-free graphs are bull-free graphs, since every bull contains a triangle. The strong perfect graph theorem was proven for bull-free graphs long before its proof for general graphs, the chromatic polynomial of the bull graph is 3 x. Two other graphs are equivalent to the bull graph. Its characteristic polynomial is − x and its Tutte polynomial is x 4 + x 3 + x 2 y

8.
Butterfly graph
–
In the mathematical field of graph theory, the butterfly graph is a planar undirected graph with 5 vertices and 6 edges. It can be constructed by joining 2 copies of the cycle graph C3 with a vertex and is therefore isomorphic to the friendship graph F2. The butterfly graph has diameter 2 and girth 3, radius 1, chromatic number 3 and it is also a 1-vertex-connected graph and a 2-edge-connected graph. There are only 3 non-graceful simple graphs with five vertices, one of them is the butterfly graph. The two others are cycle graph C5 and the complete graph K5, a graph is bowtie-free if it has no butterfly as an induced subgraph. The triangle-free graphs are graphs, since every butterfly contains a triangle. In a k-vertex-connected graph, and edge is said if the contraction of the edge results in a k-connected graph. Ando, Kaneko, Kawarabayashi and Yoshimoto proved that every k-vertex-connected bowtie-free graph has a k-contractible edge. The full automorphism group of the graph is a group of order 8 isomorphic to the Dihedral group D4. The characteristic polynomial of the graph is −2

9.
Cactus graph
–
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a graph in which every edge belongs to at most one simple cycle. A nontrivial graph is a if and only if every block is either a simple cycle or a single edge. The family of graphs in which component is a cactus is downwardly closed under graph minor operations. This graph family may be characterized by a forbidden minor. Some facility location problems which are NP-hard for general graphs, as well as some other graph problems, since cacti are special cases of outerplanar graphs, a number of combinatorial optimization problems on graphs may be solved for them in polynomial time. Cacti represent electrical circuits that have useful properties, an early application of cacti was associated with the representation of op-amps. Cacti have also recently used in comparative genomics as a way of representing the relationship between different genomes or parts of genomes. If a cactus is connected, and each of its vertices belongs to at most two blocks, then it is called a Christmas cactus. Cacti were first studied under the name of Husimi trees, bestowed on them by Frank Harary, the same Harary–Uhlenbeck paper reserves the name cactus for graphs of this type in which every cycle is a triangle, but now allowing cycles of all lengths is standard. Meanwhile, the name Husimi tree commonly came to refer to graphs in which block is a complete graph. Application of Cactus Graphs in Analysis and Design of Electronic Circuits

10.
Circle packing theorem
–
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a collection of circles whose interiors are disjoint. The intersection graph of a packing is the graph having a vertex for each circle. Coin graphs are connected, simple, and planar. A maximal planar graph G is a finite planar graph to which no more edges can be added while preserving planarity. Such a graph always has a planar embedding, in which every face of the embedding is a triangle. In other words, every planar graph G is the 1-skeleton of a simplicial complex which is homeomorphic to the sphere. The circle packing theorem guarantees the existence of a circle packing with finitely many circles whose intersection graph is isomorphic to G, as the following theorem states more formally, every maximal planar graph can have at most one packing. Thurston observes that this uniqueness is a consequence of the Mostow rigidity theorem, to see this, let G be represented by a circle packing. These two sets of planes meet at angles, and form the generators of a reflection group whose fundamental domain can be viewed as a hyperbolic manifold. Given two packings for the same graph G, one may apply reflections and Möbius transformations to make the outer circles in these two packings correspond to other and have the same radii. But the sum of the angles of all of these triangles surrounding the center of the triangle must be 2π in both packings, so all neighboring vertices to v must have the ratio as v itself. By applying the same argument to other circles in turn. But the outer circles have been transformed to have ratio 1, so r1/r2 =1, a conformal map between two open sets in the plane or in a higher-dimensional space is a continuous function from one set to the other that preserves the angles between any two curves. The Riemann mapping theorem, formulated by Bernhard Riemann in 1851, states that, conformal mappings have applications in mesh generation, map projection, and other areas. However, it is not always easy to construct a conformal mapping between two domains in an explicit way. At the Bieberbach conference in 1985, William Thurston conjectured that circle packings could be used to approximate conformal mappings. He then constructs a maximal planar graph G from the graph of the circles

11.
Combinatorial map
–
A combinatorial map is a combinatorial object modelling topological structures with subdivided objects. Historically, the concept was introduced informally by J. Edmonds for polyhedral surfaces which are planar graphs. It was given its first definite formal expression under the name Constellations by A. Jacques but the concept was extensively used under the name rotation by Gerhard Ringel. Youngs in their famous solution of the Heawood map-coloring problem, the term constellation was not retained and instead combinatorial map was favored. The concept was extended to represent higher-dimensional orientable subdivided objects. Combinatorial maps are used as efficient data structures in image representation and processing and this model is related to simplicial complexes and to combinatorial topology. Note that combinatorial maps were extended to generalized maps that allow also to represent non-orientable objects like the Möbius strip, a combinatorial map is a boundary representation model, it represents object by its boundaries. Several applications require a data structure to represent the subdivision of an object, for example, a 2D object can be decomposed into vertices, edges, and faces. More generally, an object is composed with cells of dimension 0 to n. Moreover, it is often necessary to represent neighboring relations between these cells. Thus, we want to all the cells of the subdivision, plus all the incidence. Intuitively, a 2-map corresponds to a graph where each edge is subdivided into two darts. The permutation σ gives, for each dart, the next dart by turning around the vertex in the orientation, the other permutation α gives, for each dart. α allows one to retrieve edges, and σ allows one to retrieve vertices and we define φ = σ o α which gives, for each dart, the next dart of the same face. So, there are two ways to represent a combinatorial map depending if the permutation is σ or φ and these two representations are dual to each other, vertices and faces are exchanged. The definition of map in any dimension is given in and, An n-dimensional combinatorial map is a -tuple M = such that, D is a finite set of darts, β1 is a permutation on D. βn are involutions on D, βi o βj is an involution if i +2 ≤ j, an n-dimensional combinatorial map represents the subdivision of a closed orientable n-dimensional space. A dart is an element which is only required to define one-to-one mappings

12.
Dodecahedron
–
In geometry, a dodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the dodecahedron, which is a Platonic solid. There are also three regular star dodecahedra, which are constructed as stellations of the convex form, all of these have icosahedral symmetry, order 120. The pyritohedron is a pentagonal dodecahedron, having the same topology as the regular one. The rhombic dodecahedron, seen as a case of the pyritohedron has octahedral symmetry. The elongated dodecahedron and trapezo-rhombic dodecahedron variations, along with the rhombic dodecahedra are space-filling, there are a large number of other dodecahedra. The convex regular dodecahedron is one of the five regular Platonic solids, the dual polyhedron is the regular icosahedron, having five equilateral triangles around each vertex. Like the regular dodecahedron, it has twelve pentagonal faces. However, the pentagons are not constrained to be regular, and its 30 edges are divided into two sets – containing 24 and 6 edges of the same length. The only axes of symmetry are three mutually perpendicular twofold axes and four threefold axes. Note that the regular dodecahedron can occur as a shape for quasicrystals with icosahedral symmetry. Its name comes from one of the two common crystal habits shown by pyrite, the one being the cube. The coordinates of the eight vertices of the cube are, The coordinates of the 12 vertices of the cross-edges are. When h =1, the six cross-edges degenerate to points, when h =0, the cross-edges are absorbed in the facets of the cube, and the pyritohedron reduces to a cube. When h = √5 − 1/2, the inverse of the golden ratio, a reflected pyritohedron is made by swapping the nonzero coordinates above. The two pyritohedra can be superimposed to give the compound of two dodecahedra as seen in the image here, the regular dodecahedron represents a special intermediate case where all edges and angles are equal. A tetartoid is a dodecahedron with chiral tetrahedral symmetry, like the regular dodecahedron, it has twelve identical pentagonal faces, with three meeting in each of the 20 vertices. However, the pentagons are not regular and the figure has no fivefold symmetry axes, although regular dodecahedra do not exist in crystals, the tetartoid form does

13.
Dual graph
–
In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, and a self-loop when the face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, the definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, historically, the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra. Graph duality is a generalization of the geometric concepts of dual polyhedra and dual tessellations. Variations of planar graph duality include a version of duality for directed graphs, however, these notions of dual graphs should not be confused with a different notion, the edge-to-vertex dual or line graph of a graph. The term dual is used because the property of being a graph is symmetric, meaning that if H is a dual of a connected graph G. When discussing the dual of a graph G, the graph G itself may be referred to as the primal graph, many other graph properties and structures may be translated into other natural properties and structures of the dual. For instance, cycles are dual to cuts, spanning trees are dual to the complements of spanning trees, graph duality can help explain the structure of mazes and of drainage basins. Dual graphs have also applied in computer vision, computational geometry, mesh generation. The unique planar embedding of a cycle graph divides the plane into two regions, the inside and outside of the cycle, by the Jordan curve theorem. However, in an n-cycle, these two regions are separated from each other by n different edges, therefore, the dual graph of the n-cycle is a multigraph with two vertices, connected to each other by n dual edges. Such a graph is called a dipole graph, conversely, the dual to an n-edge dipole graph is an n-cycle. According to Steinitzs theorem, every polyhedral graph must be planar and 3-vertex-connected, whenever two polyhedra are dual, their graphs are also dual. For instance the Platonic solids come in pairs, with the octahedron dual to the cube, the dodecahedron dual to the icosahedron. Polyhedron duality can also be extended to duality of higher dimensional polytopes, a plane graph is said to be self-dual if it is isomorphic to its dual graph. The wheel graphs provide a family of self-dual graphs coming from self-dual polyhedra. However, there also exist self-dual graphs that are not polyhedral and it follows from Eulers formula that every self-dual graph with n vertices has exactly 2n −2 edges

14.
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 Kempes erroneous proof of the four color theorem, the Errera graph is planar and has chromatic number 4, chromatic index 6, radius 3, diameter 4 and girth 3. All its vertices are of degree 5 or 6 and it is a 5-vertex-connected graph, the characteristic polynomial of the Errera graph is −22. The four color theorem states that the vertices of every graph can be colored with four colors. An erroneous proof was published in 1879 by Alfred Kempe, the four color theorem was not given a valid proof until 1976. Kempes proof can be translated into an algorithm to color planar graphs, counterexamples to his proof were found in 1890 and 1896, and later, the Fritsch graph and Soifer graph provided two smaller counterexamples. However, until the work of Kempe, these counterexamples did not show that the whole coloring algorithm fails, rather, they assumed that all but one vertex of the graph had already been colored, and showed that Kempes method failed in those precolored instances. The Errera graph, on the hand, provides a counterexample to Kempes entire method. When this method is run on the Errera graph, starting with no vertices colored, additionally, unlike the Poussin graph, all vertices in the Errera graph have degree five or more. Therefore, on this graph, it is impossible to avoid the problematic cases of Kempes method by choosing lower-degree vertices, the figure shows an example of how Kempes proof can fail for this graph. In the figure, the adjacencies between regions of this map form the Errera graph, partially four-colored with the outer region uncolored, Kempes erroneous proof follows the idea of extending partial colorings such as this one by recoloring Kempe chains, connected subgraphs that have only two colors. Any such chain can be recolored, preserving the validity of the coloring, Kempes proof has different cases depending on whether the next vertex to be colored has three, four, or five neighbors and on how those neighbors are colored. In the case shown, the vertex to be colored next is the one corresponding to the region of the map. This region cannot be colored directly, because it already has neighbors of all four different colors, the blue and yellow neighbors are connected by a single Kempe chain, preventing a swap from making them both blue or both yellow and freeing a color. Similarly, the blue and green neighbors are connected by another Kempe chain, in such a case, Kempes proof would try to simultaneously swap the colors on two Kempe chains, the left red-yellow chain and the right red-green chain. But because the blue-yellow and blue-green chains cross each other rather than staying separated, there is a region in the middle of the figure where the red-yellow and red-green chains can meet. When these two meet in the middle, the simultaneous swap causes adjacent yellow and green vertices in this middle area to both become red, producing an invalid coloring. Chemical graph theory concerns the structure of molecules and other clusters of atoms

15.
Four color theorem
–
Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions. Despite the motivation from coloring political maps of countries, the theorem is not of particular interest to mapmakers, according to an article by the math historian Kenneth May, “Maps utilizing only four colors are rare, and those that do usually require only three. Books on cartography and the history of mapmaking do not mention the four-color property, a number of false proofs and false counterexamples have appeared since the first statement of the four color theorem in 1852. Martin Gardner wrote an account of what was known at the time about the four color theorem in his September 1960 Mathematical Games column in Scientific American magazine. In 1975 Gardner revisited the topic by publishing a map said to be a counter-example in his infamous April fools hoax column of April 1975, the four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proved using a computer, Appel and Hakens approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem. Appel and Haken used a computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps, showing this required hundreds of pages of hand analysis. Appel and Haken concluded that no smallest counterexamples exist because any must contain, yet do not contain and this contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by all mathematicians because the proof was infeasible for a human to check by hand. Since then the proof has gained acceptance, although doubts remain. To dispel remaining doubt about the Appel–Haken proof, a proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour. Additionally, in 2005, the theorem was proved by Georges Gonthier with general purpose theorem proving software, the intuitive statement of the four color theorem, i. e. First, all corners, points that belong to three or more countries, must be ignored. In addition, bizarre maps can require more than four colors, second, for the purpose of the theorem, every country has to be a connected region, or contiguous. In the real world, this is not true, because all the territory of a particular country must be the same color, four colors may not be sufficient. For instance, consider a simplified map, In this map and this map then requires five colors, since the two A regions together are contiguous with four other regions, each of which is contiguous with all the others. A similar construction also applies if a color is used for all bodies of water. For maps in which more than one country may have multiple disconnected regions, a simpler statement of the theorem uses graph theory

16.
Left-right planarity test
–
In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested. For any depth-first search of a graph G, the edges encountered when discovering a vertex for the first time define a depth-first search tree T of G. This is a Trémaux tree, meaning that the edges each connect a pair of vertices that are related to each other as an ancestor. Three types of patterns can be used to define two relations between pairs of edges, named the T-alike and T-opposite relations. In the following figures, simple circle nodes represent vertices, double circle nodes represent subtrees, twisted segments represent tree paths, the root of each tree is shown at the bottom of the figure. In the first figure, the edges labeled α and β are T-alike, meaning that, at the endpoints nearest the root of the tree, they will both be on the same side of the tree in every planar drawing. In the next two figures, the edges with the labels are T-opposite, meaning that they will be on different sides of the tree in every planar drawing

17.
Friendship graph
–
In the mathematical field of graph theory, the friendship graph Fn is a planar undirected graph with 2n+1 vertices and 3n edges. The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex, by construction, the friendship graph Fn is isomorphic to the windmill graph Wd. It is unit distance with girth 3, diameter 2 and radius 1, the graph F2 is isomorphic to the butterfly graph. Informally, if a group of people has the property that every pair of people has exactly one friend in common, however, for infinite graphs, there can be many different graphs with the same cardinality that have this property. A combinatorial proof of the theorem was given by Mertzios. Another proof was given by Craig Huneke, the friendship graph has chromatic number 3 and chromatic index 2n. Its chromatic polynomial can be deduced from the polynomial of the cycle graph C3 and is equal to n n x. The friendship graph Fn is edge-graceful if and only if n is odd and it is graceful if and only if n ≡0 or n ≡1. According to extremal graph theory, every graph with many edges must contain a k-fan as a subgraph

18.
Frucht graph
–
In the mathematical field of graph theory, the Frucht graph is a 3-regular 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 chromatic number 3, chromatic index 3, radius 3, and diameter 4. As with every Halin graph, the Frucht graph is polyhedral and Hamiltonian, the Frucht graph can be constructed from the LCF notation. The Frucht graph is one of the two smallest cubic graphs possessing only a single graph automorphism, the identity, such graphs are called asymmetric graphs. The characteristic polynomial of the Frucht graph is x

19.
Graphic matroid
–
In matroid theory, a discipline within mathematics, a graphic matroid is a matroid whose independent sets are the forests in a given undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids, a matroid that is both graphic and co-graphic is called a planar matroid, these are exactly the graphic matroids formed from planar graphs. If G is a graph, and F is the family of sets of edges that form forests in G. Thus, F forms the independent sets of a matroid, called the graphic matroid of G or M, more generally, a matroid is called graphic whenever it is isomorphic to the graphic matroid of a graph, regardless of whether its elements are themselves edges in a graph. The bases of a graphic matroid M are the forests of G. The corank of the matroid is known as the circuit rank or cyclomatic number. The closure cl of a set S of edges in M is a flat consisting of the edges that are not independent of S. In the lattice of flats of this matroid, there is an order relation x ≤ y whenever the corresponding to flat x is a refinement of the partition corresponding to flat y. Thus, the lattice of flats of the matroid of K n is naturally isomorphic to the lattice of partitions of an n -element set. Since the lattices of flats of matroids are exactly the geometric lattices, the graphic matroid of a graph G can be defined as the column matroid of any oriented incidence matrix of G. Such a matrix has one row for each vertex, and one column for each edge, the column matroid of this matrix has as its independent sets the linearly independent subsets of columns. If a set of edges contains a cycle, then the corresponding columns sum to zero, conversely, if a set of edges forms a forest, then by repeatedly removing leaves from this forest it can be shown by induction that the corresponding set of columns is independent. Therefore, the matrix is isomorphic to M. This method of representing graphic matroids works regardless of the field over which the incidence is defined, therefore, graphic matroids form a subset of the regular matroids, matroids that have representations over all possible fields. Graphic matroids are connected if and only if the graph is both connected and 2-vertex-connected. The first three of these are the forbidden minors for the regular matroids, and the duals of M and M are regular, if a matroid is graphic, its dual cannot contain the duals of these five forbidden minors. Thus, the dual must also be regular, and cannot contain as minors the two graphic matroids M and M, if G is planar, the dual of M is the graphic matroid of the dual graph of G. While G may have multiple dual graphs, their graphic matroids are all isomorphic, a minimum weight basis of a graphic matroid is a minimum spanning tree

20.
Grinberg's theorem
–
In graph theory, Grinbergs theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. The result has been used to construct non-Hamiltonian planar graphs with further properties. This theorem was proved by Latvian mathematician Emanuel Grinberg in 1968, let G be a finite planar graph with a Hamiltonian cycle C, with a fixed planar embedding. Denote by ƒk and gk the number of faces of the embedding that are inside and outside of C. The proof is an consequence of Eulers formula. For instance, for the graph in the figure, all the faces have 5 or 8 sides. For any planar graph, the faces whose number of sides is 2 mod 3 contribute 0 mod 3 to the sum in Grinbergs theorem, however, the other faces contribute a number that nonzero mod 3, regardless of whether they are inside or outside the Hamiltonian cycle. So, when there is only one face that contributes an amount, it is not possible for the total to be zero. Grinberg used his theorem to find non-Hamiltonian cubic polyhedral graphs with high cyclic edge connectivity, the cyclic edge connectivity of a graph is the smallest number of edges that may be deleted in such a way that the remaining graph has more than one cyclic component. The 46-vertex Tutte graph, and the smaller cubic non-Hamiltonian polyhedral graphs derived from it, have cyclic edge connectivity three. In the example shown, all of the faces have either five or eight edges, both of which are numbers that are 2 mod 3, but the unbounded face has nine edges. Therefore, by the Corollary to Grinbergs theorem, the graph cannot be Hamiltonian, Grinbergs theorem has also been used to find planar hypohamiltonian graphs, again by making all but one face have a number of edges congruent to 2 mod 3. In order to satisfy Grinbergs theorem, a Hamiltonian cycle would have to one of the 4- or 7-edge faces from the other four. There exist planar graphs in which all faces have five or eight sides. It is not possible to use Grinbergs theorem to find counterexamples to Barnettes conjecture, for, in such graphs, there always exists a partition of the faces into two subsets satisfying Grinbergs theorem, regardless of Hamiltonicity. Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math, english translation by Dainis Zeps, arXiv,0908.2563. Krooss, André, Die Barnettesche Vermutung und die Grinbergsche Formel, seria Matematică-Informatică,31, 59–65, MR2153849. Malkevitch, Joseph, Eulers Polyhedral Formula, Part II, Feature Column, thomassen, Carsten, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Mathematics,14, 377–389, doi,10. 1016/0012-365X90071-6, MR0422086

21.
Halin graph
–
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. Thus, the forms the outer face of the Halin graph. Every Halin graph has a Hamiltonian cycle through all its vertices, the Halin graphs can be recognized in linear time. Many computational problems that are hard on other kinds of graphs, such as finding Hamiltonian cycles. A star is a tree with one internal vertex. Applying the Halin graph construction to a star produces a wheel graph, the Frucht graph, one of the two smallest cubic graphs with no nontrivial graph automorphisms, is also a Halin graph. Every Halin graph is 3-connected, meaning that it is not possible to delete two vertices from it and disconnect the remaining vertices and it is edge-minimal 3-connected, meaning that if any one of its edges is removed, the remaining graph will no longer be 3-connected. By Steinitzs theorem, as a 3-connected planar graph, it can be represented as the set of vertices and edges of a convex polyhedron, that is, it is a polyhedral graph. And, as with every polyhedral graph, its planar embedding is unique up to the choice of which of its faces is to be the outer face, every Halin graph is a Hamiltonian graph, and every edge of the graph belongs to a Hamiltonian cycle. Moreover, any Halin graph remains Hamiltonian after deletion of any vertex, because every tree without vertices of degree 2 contains two leaves that share the same parent, every Halin graph contains a triangle. In particular, it is not possible for a Halin graph to be a triangle-free graph nor a bipartite graph. More strongly, every Halin graph is almost pancyclic, in the sense that it has cycles of all lengths from 3 to n with the exception of a single even length. Moreover, any Halin graph remains almost pancyclic if an edge is contracted. The weak dual of a planar graph has vertices corresponding to bounded faces of the planar graph. The weak dual of a Halin graph is biconnected and outerplanar. The incidence chromatic number of a Halin graph G with maximum degree Δ greater than four is Δ +1. This is the number of colors needed to color all pairs where v is a vertex of the graph, pairs that share a vertex or that share an edge are not allowed to have the same color. In addition, a pair cannot have the color as another pair that uses the other endpoint of e

22.
Harborth's conjecture
–
In mathematics, Harborths conjecture states that every planar graph has a planar drawing in which all edge lengths are integers. This conjecture is named after Heiko Harborth, and would strengthen Fárys theorem on the existence of drawings for every planar graph. For this reason, a drawing with integer edge lengths is known as an integral Fáry embedding. Despite much subsequent research, Harborths conjecture remains unsolved, although Harborths conjecture is not known to be true for all planar graphs, it has been proven for several special kinds of planar graph. One class of graphs that have integral Fáry embeddings are the graphs that can be reduced to the empty graph by a sequence of operations of two types, Removing a vertex of degree at most two. Replacing a vertex of degree three by an edge between two of its neighbors, the distances in such an embedding can be made into integers by scaling the embedding by an appropriate factor. In particular, the graphs that can be reduced to the empty graph by the only of vertices of degree at most two include both the outerplanar graphs and the series-parallel graphs. Additionally, integral Fáry embeddings are known for each of the five Platonic solids, a stronger version of Harborths conjecture, posed by Kleber, asks whether every planar graph has a planar drawing in which the vertex coordinates as well as the edge lengths are all integers. It is known to be true for 3-regular graphs, for graphs that have maximum degree 4 but are not 4-regular, another unsolved problem in geometry, the Erdős–Ulam problem, concerns the existence of dense subsets of the plane in which all distances are rational numbers. If such a subset existed, it would form a point set that could be used to draw all planar graphs with rational edge lengths. However, Ulam conjectured that dense rational-distance sets do not exist, according to the Erdős–Anning theorem, infinite non-collinear point sets with all distances being integers cannot exist. This does not rule out the existence of sets with all distances rational, but it does imply that in any such set the denominators of the rational distances must grow arbitrarily large

23.
Herschel graph
–
In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. However, Herschels paper described solutions for the Icosian game only on the graphs of the tetrahedron and regular icosahedron. The Herschel graph is a graph, it can be drawn in the plane with none of its edges crossing. It is also 3-vertex-connected, the removal of any two of its vertices leaves a connected subgraph, therefore, by Steinitzs theorem, the Herschel graph is a polyhedral graph, there exists a convex polyhedron having the Herschel graph as its skeleton. The Herschel graph is also a bipartite graph, its vertices can be separated into two subsets of five and six respectively, such that every edge has an endpoint in each subset. As with any graph, the Herschel graph is a perfect graph. It has also chromatic index 4, girth 4, radius 3, because it is a bipartite graph that has an odd number of vertices, the Herschel graph does not contain a Hamiltonian cycle. Thus, a cycle passing once through each of the eleven vertices cannot exist in the Herschel graph, T. Tutte provided a counterexample, the much larger Tutte graph. A refinement of Taits conjecture, Barnettes conjecture that every bipartite 3-regular polyhedral graph is Hamiltonian, the Herschel graph also provides an example of a polyhedral graph for which the medial graph cannot be decomposed into two edge-disjoint Hamiltonian cycles

24.
Kuratowski's theorem
–
In graph theory, Kuratowskis theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 or of K3,3. Planar graphs are often drawn with straight line segments representing their edges, a subdivision of a graph is a graph formed by subdividing its edges into paths of one or more edges. Equivalently, a graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 or K3,3. If G is a graph contains a subgraph H that is a subdivision of K5 or K3,3. With this notation, Kuratowskis theorem can be expressed succinctly, a graph is planar if, the two graphs K5 and K3,3 are nonplanar, as may be shown either by a case analysis or an argument involving Eulers formula. Therefore, a graph contains a Kuratowski subgraph cannot be planar. The more difficult direction in proving Kuratowskis theorem is to show that, if a graph is nonplanar, a Kuratowski subgraph of a nonplanar graph can be found in linear time, as measured by the size of the input graph. This allows the correctness of a planarity testing algorithm to be verified for nonplanar inputs, usually, non-planar graphs contain a large number of Kuratowski-subgraphs. The extraction of these subgraphs is needed, e. g. in branch and it is possible to extract a large number of Kuratowski subgraphs in time dependent on their total size. Kazimierz Kuratowski published his theorem in 1930, the theorem was independently proved by Orrin Frink and Paul Smith, also in 1930, but their proof was never published. The special case of planar graphs was also independently proved by Karl Menger in 1930. Since then, several new proofs of the theorem have been discovered, however, as Pontryagin never published his proof, this usage has not spread to other places. A closely related result, Wagners theorem, characterizes the planar graphs by their minors in terms of the two forbidden graphs K5 and K3,3. Kelmans–Seymour conjecture, that 5-connected nonplanar graphs contain a subdivision of K5

25.
Ladder graph
–
In the mathematical field of graph theory, the ladder graph Ln is a planar undirected graph with 2n vertices and n+2 edges. The ladder graph can be obtained as the Cartesian product of two graphs, one of which has only one edge, Ln,1 = Pn × P1. Adding two more crossed edges connecting the four vertices of a ladder graph produces a cubic graph. By construction, the ladder graph Ln is isomorphic to the grid graph G2, n and it is Hamiltonian with girth 4 and chromatic index 3. The chromatic number of the graph is 2 and its chromatic polynomial is x. The circular ladder graph CLn is the Cartesian product of a cycle of length n≥3, in symbols, CLn = Cn × P1. It has 2n nodes and 3n edges, like the ladder graph, it is connected, planar and Hamiltonian, but it is bipartite if and only if n is even

26.
Medial graph
–
In the mathematical discipline of graph theory, the medial graph of plane graph G is another graph M that represents the adjacencies between edges in the faces of G. Given a connected plane graph G, its medial graph M has a vertex for each edge of G, the medial graph of a disconnected graph is the disjoint union of the medial graphs of each connected component. The definition of medial graph also extends without modification to graph embeddings on surfaces of higher genus, the medial graph of any plane graph is a 4-regular plane graph. For any plane graph G, the graph of G. Conversely, for any 4-regular plane graph H, the two plane graphs with medial graph H are dual to each other. Since the medial graph depends on an embedding, the medial graph of a planar graph is not unique. In the picture, the red graphs are not isomorphic because the two vertices with self loops share an edge in one graph but not in the other, every 4-regular plane graph is the medial graph of some plane graph. For a connected 4-regular plane graph H, a planar graph G with H as its graph can be constructed as follows. Color the faces of H with just two colors, which is possible since H is Eulerian, the vertices in G correspond to the faces of a single color in H. These vertices are connected by an edge for each shared by their corresponding faces in H. Note that performing this construction using the faces of the color as the vertices produces the dual graph of G. Since the Tutte polynomial is invariant under embeddings, this shows that every medial graph has the same sum of these weighted Eulerian orientations. The medial graph definition can be extended to include an orientation, first, the faces of the medial graph are colored black if they contain a vertex of the original graph and white otherwise. This coloring causes each edge of the graph to be bordered by one black face. Then each edge is oriented so that the face is on its left. A plane graph and its dual do not have the same directed medial graph, using the directed medial graph, one can effectively generalize the result on evaluations of the Tutte polynomial at. Line graph Knots and graphs Tait graph Rectification - The equivalent operation on polyhedrons Brylawski, Thomas, Oxley, the Tutte Polynomial and Its Applications

27.
Moser spindle
–
In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, the Moser spindle has also been called the Hajós graph after György Hajós, as it can be viewed as an instance of the Hajós construction. However, the name Hajós graph has also applied to a different graph. As a unit distance graph, the Moser spindle is formed by two rhombi with 60 and 120 degree angles, so that the sides and short diagonals of the rhombi form equilateral triangles. The two rhombi are placed in the plane, sharing one of their vertices, in such a way that the remaining two acute-angled vertices are a unit distance apart from each other. The eleven edges of the graph are the eight rhombus sides, the Moser spindle may also be constructed graph-theoretically, without reference to a geometric embedding, using the Hajós construction starting with two complete graphs on four vertices. Another way of constructing the Moser spindle is as the complement graph of the formed from the utility graph K3,3 by subdividing one of its edges. That is, it asks for the number of the infinite graph whose vertices are all the points in the plane. This contradiction shows that three colors are impossible, so at least four colors are necessary, four colors are also sufficient to color the Moser spindle, a fact that follows for instance from the fact that its degeneracy is three. An alternative proof that the Moser spindle requires four colors follows from the Hajós construction, both of the complete graphs from which the Moser spindle is formed require four colors, and the Hajós construction preserves this property. Even more directly, each independent set in the Moser spindle has at most two vertices, so it takes at least four independent sets to all seven vertices. Since the Moser spindle is a subgraph of the infinite unit distance graph of the plane, however, the best upper bound for the chromatic number of the plane is seven, significantly higher than the number of colors required for the Moser spindle. The Moser spindle is a graph, meaning that it can be drawn without crossings in the plane. However, it is not possible to such a drawing with straight line edges that is also a unit distance drawing. The Moser spindle is also a Laman graph, meaning that it forms a rigid system when embedded in the plane. The complement graph of the Moser graph is a triangle-free graph, but then the three copies of this vertex form a translate of T. Weisstein, Eric W. Moser Spindle

28.
Nested triangles graph
–
It can also be formed geometrically, by gluing together n/3 −1 triangular prisms on their triangular faces. This graph, and graphs related to it, have been frequently used in graph drawing to prove lower bounds on the area requirements of various styles of drawings. The nested triangles graph with two triangles is the graph of the prism, and the nested triangles graph with three triangles is the graph of the triangular bifrustum. More generally, because the nested triangles graphs are planar and 3-vertex-connected, however, using right prisms, this gluing process will cause the rectangular faces of adjacent prisms to be coplanar, so the result will not be strictly convex. For drawings in which the face may be freely chosen. Frati & Patrignani showed that this graph, and any graph formed by adding diagonals to its quadrilaterals, when no extra diagonals are added the nested triangles graph itself can be drawn in even smaller area, approximately n/3 × n/2, as shown. Closing the gap between the 2n2/9 upper bound and the lower bound on drawing area for completions of the nested triangle graph remains an open problem