The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree,[1][2] either making all its edges point away from the root—in which case it is called an arborescence,[3]branching,[4] or out-tree[4]—or making all its edges point towards the root—in which case it is called an anti-arborescence[5] or in-tree.[6] A rooted tree itself has been defined by some authors as a directed graph.[7][8][9]

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

G is connected and has n − 1 edges.

G is connected, and every subgraph of G includes at least one vertex with zero or one incident edges. (That is, G is connected and 1-degenerate.)

G has no simple cycles and has n − 1 edges.

As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally not considered to be a tree: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not 0-connected (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more vertex than edges" relation. It may, however, be considered as a forest consisting of zero trees.

An internal vertex (or inner vertex or branch vertex) is a vertex of degree at least 2. Similarly, an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1.

An irreducible tree (or series-reduced tree) is a tree in which there is no vertex of degree 2.

A forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Equivalently, a forest is an undirected acyclic graph. As special cases, an empty graph, a single tree, and the discrete graph on a set of vertices (that is, the graph with these vertices that has no edges), are examples of forests.
Since for every tree V - E = 1, we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges. TV - TE = number of trees in a forest.

A polytree[11] (or oriented tree[12][13] or singly connected network[14]) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.

A directed tree is a directed graph which would be a tree if the directions on the edges were ignored, i.e. a polytree. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).

A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence, branching, or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree. The tree-order is the partial ordering on the vertices of a tree with u < v if and only if the unique path from the root to v passes through u. A rooted tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this tree-order whenever those ends are vertices of the tree (Diestel 2005, p. 15). Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure.

In a context where trees are supposed to have a root, a tree without any designated root is called a free tree.

A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices are typically given the labels 1, 2, …, n. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v).

In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex v is a vertex of which v is the parent. A descendant of any vertex v is any vertex which is either the child of v or is (recursively) the descendant of any of the children of v. A sibling to a vertex v is any other vertex on the tree which has the same parent as v. The root is an external vertex if it has precisely one child. A leaf is different from the root.

The height of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. The height of the tree is the height of the root. The depth of a vertex is the length of the path to its root (root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL trees in particular. The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no vertices, if such are allowed) has depth and height −1.

An ordered tree (or plane tree) is a rooted tree in which an ordering is specified for the children of each vertex.[16] This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane, with the root at the top and the children of each vertex lower than that vertex. Given an embedding of a rooted tree in the plane, if one fixes a direction of children, say left to right, then an embedding gives an ordering of the children. Conversely, given an ordered tree, and conventionally drawing the root at the top, then the child vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding .

There exist connected graphs with uncountably many vertices which do not admit a normal spanning tree (Diestel 2005, Prop. 8.5.2).

Every finite tree with n vertices, with n > 1, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of path graphs; the maximal number, n − 1, is attained only by star graphs. The number of leaves is at least the maximal vertex degree.

For any three vertices in a tree, the three paths between them have exactly one vertex in common.

Otter showed that any n-vertex tree has either a unique center vertex, whose removal splits the tree into subtrees of fewer than n/2 vertices, or a unique center edge, whose removal splits the tree into two subtrees of exactly n/2 vertices.

with the values C and α known to be approximately 0.534949606… and 2.95576528565… (sequence A051491 in the OEIS), respectively. (Here, f ~ g means that limn→∞f /g = 1.) This is a consequence of his asymptotic estimate for the number r(n) of unlabeled rooted trees with n vertices:

1.
Mathematics
–
Mathematics is the study of topics such as quantity, structure, space, and change. There is a range of views among mathematicians and philosophers as to the exact scope, Mathematicians seek out patterns and use them to formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proof, when mathematical structures are good models of real phenomena, then mathematical reasoning can provide insight or predictions about nature. Through the use of abstraction and logic, mathematics developed from counting, calculation, measurement, practical mathematics has been a human activity from as far back as written records exist. The research required to solve mathematical problems can take years or even centuries of sustained inquiry, rigorous arguments first appeared in Greek mathematics, most notably in Euclids Elements. Galileo Galilei said, The universe cannot be read until we have learned the language and it is written in mathematical language, and the letters are triangles, circles and other geometrical figures, without which means it is humanly impossible to comprehend a single word. Without these, one is wandering about in a dark labyrinth, carl Friedrich Gauss referred to mathematics as the Queen of the Sciences. Benjamin Peirce called mathematics the science that draws necessary conclusions, David Hilbert said of mathematics, We are not speaking here of arbitrariness in any sense. Mathematics is not like a game whose tasks are determined by arbitrarily stipulated rules, rather, it is a conceptual system possessing internal necessity that can only be so and by no means otherwise. Albert Einstein stated that as far as the laws of mathematics refer to reality, they are not certain, Mathematics is essential in many fields, including natural science, engineering, medicine, finance and the social sciences. Applied mathematics has led to entirely new mathematical disciplines, such as statistics, Mathematicians also engage in pure mathematics, or mathematics for its own sake, without having any application in mind. There is no clear line separating pure and applied mathematics, the history of mathematics can be seen as an ever-increasing series of abstractions. The earliest uses of mathematics were in trading, land measurement, painting and weaving patterns, in Babylonian mathematics elementary arithmetic first appears in the archaeological record. Numeracy pre-dated writing and numeral systems have many and diverse. Between 600 and 300 BC the Ancient Greeks began a study of mathematics in its own right with Greek mathematics. Mathematics has since been extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries continue to be made today, the overwhelming majority of works in this ocean contain new mathematical theorems and their proofs. The word máthēma is derived from μανθάνω, while the modern Greek equivalent is μαθαίνω, in Greece, the word for mathematics came to have the narrower and more technical meaning mathematical study even in Classical times

2.
Computer science
–
Computer science is the study of the theory, experimentation, and engineering that form the basis for the design and use of computers. An alternate, more succinct definition of science is the study of automating algorithmic processes that scale. A computer scientist specializes in the theory of computation and the design of computational systems and its fields can be divided into a variety of theoretical and practical disciplines. Some fields, such as computational complexity theory, are highly abstract, other fields still focus on challenges in implementing computation. Human–computer interaction considers the challenges in making computers and computations useful, usable, the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, further, algorithms for performing computations have existed since antiquity, even before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623, in 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner. He may be considered the first computer scientist and information theorist, for, among other reasons and he started developing this machine in 1834, and in less than two years, he had sketched out many of the salient features of the modern computer. A crucial step was the adoption of a card system derived from the Jacquard loom making it infinitely programmable. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information, when the machine was finished, some hailed it as Babbages dream come true. During the 1940s, as new and more powerful computing machines were developed, as it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. Computer science began to be established as an academic discipline in the 1950s. The worlds first computer science program, the Cambridge Diploma in Computer Science. The first computer science program in the United States was formed at Purdue University in 1962. Since practical computers became available, many applications of computing have become distinct areas of study in their own rights and it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM704 and later the IBM709 computers, still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, and you would have to start the whole process over again. During the late 1950s, the science discipline was very much in its developmental stages. Time has seen significant improvements in the usability and effectiveness of computing technology, modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base

3.
Binary tree
–
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a tree is a triple. Some authors allow the tree to be the empty set as well. From a graph theory perspective, binary trees as defined here are actually arborescences, a binary tree may thus be also called a bifurcating arborescence—a term which appears in some very old programming books, before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than a directed graph, some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted. A binary tree is a case of an ordered K-ary tree. In computing, binary trees are used solely for their structure. Much more typical is to define a function on the nodes. Binary trees labelled this way are used to implement binary search trees and binary heaps, the designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular it is significant in binary search trees. In mathematics, what is termed binary tree can vary significantly from author to author, some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and dont necessarily order the children either. Another way of defining a full tree is a recursive definition. A full binary tree is either, A single vertex, a graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. This also does not establish the order of children, but does fix a specific root node, to actually define a binary tree in general, we must allow for the possibility that only one of the children may be empty. An artifact, which in some textbooks is called a binary tree is needed for that purpose. Another way of imagining this construction is to instead of the empty set a different type of node—for instance square nodes if the regular ones are circles. A binary tree is a tree that is also an ordered tree in which every node has at most two children. A rooted tree naturally imparts a notion of levels, thus for every node a notion of children may be defined as the connected to it a level below. Ordering of these children makes possible to distinguish left child from right child, but this still doesnt distinguish between a node with left but not a right child from a one with right but no left child

4.
Connectivity (graph theory)
–
It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network, a graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices, a graph that is not connected is disconnected. A graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints, a graph with just one vertex is connected. An edgeless graph with two or more vertices is disconnected, in an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. If the two vertices are connected by a path of length 1, i. e. by a single edge. A graph is said to be connected if every pair of vertices in the graph is connected, a connected component is a maximal connected subgraph of G. Each vertex belongs to exactly one connected component, as does each edge, a directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected graph. It is connected if it contains a path from u to v or a directed path from v to u for every pair of vertices u, v. It is strongly connected, diconnected, or simply strong if it contains a path from u to v. The strong components are the maximal strongly connected subgraphs, a cut, vertex cut, or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. The connectivity or vertex connectivity κ is the size of a minimal vertex cut, a graph is called k-connected or k-vertex-connected if its vertex connectivity is k or greater. In particular, a graph with n vertices, denoted Kn, has no vertex cuts at all. A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ is the size of a smallest vertex cut separating u and v. Local connectivity is symmetric for undirected graphs, a graph G which is connected but not 2-connected is sometimes called separable. Analogous concepts can be defined for edges, in the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. More generally, a cut of G is a set of edges whose removal renders the graph disconnected. A graph is called k-edge-connected if its edge connectivity is k or greater, if u and v are vertices of a graph G, then a collection of paths between u and v is called independent if no two of them share a vertex

5.
Arthur Cayley
–
Arthur Cayley F. R. S. was a British mathematician. He helped found the modern British school of pure mathematics, as a child, Cayley enjoyed solving complex maths problems for amusement. He entered Trinity College, Cambridge, where he excelled in Greek, French, German and he worked as a lawyer for 14 years. He postulated the Cayley–Hamilton theorem—that every square matrix is a root of its own characteristic polynomial and he was the first to define the concept of a group in the modern way—as a set with a binary operation satisfying certain laws. Formerly, when mathematicians spoke of groups, they had meant permutation groups, cayleys theorem is named in honour of Cayley. Arthur Cayley was born in Richmond, London, England, on 16 August 1821 and his father, Henry Cayley, was a distant cousin of Sir George Cayley the aeronautics engineer innovator, and descended from an ancient Yorkshire family. He settled in Saint Petersburg, Russia, as a merchant and his mother was Maria Antonia Doughty, daughter of William Doughty. According to some writers she was Russian, but her fathers name indicates an English origin and his brother was the linguist Charles Bagot Cayley. Arthur spent his first eight years in Saint Petersburg, in 1829 his parents were settled permanently at Blackheath, near London. Arthur was sent to a private school, at age 14 he was sent to Kings College School. The schools master observed indications of genius and advised the father to educate his son not for his own business, as he had intended. At the unusually early age of 17 Cayley began residence at Trinity College, Cambridge, the cause of the Analytical Society had now triumphed, and the Cambridge Mathematical Journal had been instituted by Gregory and Robert Leslie Ellis. To this journal, at the age of twenty, Cayley contributed three papers, on subjects that had been suggested by reading the Mécanique analytique of Lagrange, cayleys tutor at Cambridge was George Peacock and his private coach was William Hopkins. He finished his course by winning the place of Senior Wrangler. His next step was to take the M. A. degree and he continued to reside at Cambridge University for four years, during which time he took some pupils, but his main work was the preparation of 28 memoirs to the Mathematical Journal. Because of the tenure of his fellowship it was necessary to choose a profession, like De Morgan, Cayley chose law. He made a specialty of conveyancing and it was while he was a pupil at the bar examination that he went to Dublin to hear Hamiltons lectures on quaternions. During this period of his life, extending over fourteen years, at Cambridge University the ancient professorship of pure mathematics is denominated by the Lucasian, and is the chair that had been occupied by Isaac Newton

6.
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, nodes, or points which are connected by edges, arcs, Graphs are one of the prime objects of study in discrete mathematics. Refer to the glossary of graph theory for basic definitions in graph theory, the following are some of the more basic ways of defining graphs and related mathematical structures. To avoid ambiguity, this type of graph may be described precisely as undirected, other senses of graph stem from different conceptions of the edge set. In one more generalized notion, V is a set together with a relation of incidence that associates with each two vertices. In another generalized notion, E is a multiset of unordered pairs of vertices, Many authors call this type of object a multigraph or pseudograph. All of these variants and others are described more fully below, the vertices belonging to an edge are called the ends or end vertices of the edge. A vertex may exist in a graph and not belong to an edge, V and E are usually taken to be finite, and many of the well-known results are not true for infinite graphs because many of the arguments fail in the infinite case. The order of a graph is |V|, its number of vertices, the size of a graph is |E|, its number of edges. The degree or valency of a vertex is the number of edges that connect to it, for an edge, graph theorists usually use the somewhat shorter notation xy. Graphs can be used to model many types of relations and processes in physical, biological, social, Many practical problems can be represented by graphs. Emphasizing their application to real-world systems, the network is sometimes defined to mean a graph in which attributes are associated with the nodes and/or edges. In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the structure of a website can be represented by a directed graph, in which the vertices represent web pages. A similar approach can be taken to problems in media, travel, biology, computer chip design. The development of algorithms to handle graphs is therefore of major interest in computer science, the transformation of graphs is often formalized and represented by graph rewrite systems. Graph-theoretic methods, in forms, have proven particularly useful in linguistics. Traditionally, syntax and compositional semantics follow tree-based structures, whose power lies in the principle of compositionality

7.
On-Line Encyclopedia of Integer Sequences
–
The On-Line Encyclopedia of Integer Sequences, also cited simply as Sloanes, is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs, Sloane continues to be involved in the OEIS in his role as President of the OEIS Foundation. OEIS records information on integer sequences of interest to professional mathematicians and amateurs, and is widely cited. As of 30 December 2016 it contains nearly 280,000 sequences, the database is searchable by keyword and by subsequence. Neil Sloane started collecting integer sequences as a student in 1965 to support his work in combinatorics. The database was at first stored on punched cards and he published selections from the database in book form twice, A Handbook of Integer Sequences, containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372. The Encyclopedia of Integer Sequences with Simon Plouffe, containing 5,488 sequences and these books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an e-mail service, as a spin-off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year, Sloane has personally managed his sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database. In 2004, Sloane celebrated the addition of the 100, 000th sequence to the database, A100000, in 2006, the user interface was overhauled and more advanced search capabilities were added. In 2010 an OEIS wiki at OEIS. org was created to simplify the collaboration of the OEIS editors and contributors, besides integer sequences, the OEIS also catalogs sequences of fractions, the digits of transcendental numbers, complex numbers and so on by transforming them into integer sequences. Sequences of rationals are represented by two sequences, the sequence of numerators and the sequence of denominators, important irrational numbers such as π =3.1415926535897. are catalogued under representative integer sequences such as decimal expansions, binary expansions, or continued fraction expansions. The OEIS was limited to plain ASCII text until 2011, yet it still uses a form of conventional mathematical notation. Greek letters are represented by their full names, e. g. mu for μ. Every sequence is identified by the letter A followed by six digits, sometimes referred to without the leading zeros, individual terms of sequences are separated by commas. Digit groups are not separated by commas, periods, or spaces, a represents the nth term of the sequence. Zero is often used to represent non-existent sequence elements, for example, A104157 enumerates the smallest prime of n² consecutive primes to form an n×n magic square of least magic constant, or 0 if no such magic square exists. The value of a is 2, a is 1480028129, but there is no such 2×2 magic square, so a is 0

8.
Graph coloring
–
In graph theory, graph coloring is a special case of graph labeling, it is an assignment of labels traditionally called colors to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a such that no two adjacent vertices share the same color, this is called a vertex coloring. Vertex coloring is the point of the subject, and other coloring problems can be transformed into a vertex version. For example, a coloring of a graph is just a vertex coloring of its line graph. However, non-vertex coloring problems are often stated and studied as is and that is partly for perspective, and partly because some problems are best studied in non-vertex form, as for instance is edge coloring. The convention of using colors originates from coloring the countries of a map and this was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or nonnegative integers as the colors, in general, one can use any finite set as the color set. The nature of the coloring problem depends on the number of colors, graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned and it has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still an active field of research. Note, Many terms used in this article are defined in Glossary of graph theory, the first results about graph coloring deal almost exclusively with planar graphs in the form of the coloring of maps. Guthrie’s brother passed on the question to his mathematics teacher Augustus de Morgan at University College, arthur Cayley raised the problem at a meeting of the London Mathematical Society in 1879. The same year, Alfred Kempe published a paper that claimed to establish the result, for his accomplishment Kempe was elected a Fellow of the Royal Society and later President of the London Mathematical Society. In 1890, Heawood pointed out that Kempe’s argument was wrong, however, in that paper he proved the five color theorem, saying that every planar map can be colored with no more than five colors, using ideas of Kempe. The proof went back to the ideas of Heawood and Kempe, the proof of the four color theorem is also noteworthy for being the first major computer-aided proof. Kempe had already drawn attention to the general, non-planar case in 1879, the conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002. One of the applications of graph coloring, register allocation in compilers, was introduced in 1981

9.
Directed acyclic graph
–
In mathematics and computer science, a directed acyclic graph, is a finite directed graph with no directed cycles. Equivalently, a DAG is a graph that has a topological ordering. DAGs can model different kinds of information. Similarly, topological orderings of DAGs can be used to order the compilation operations in a makefile, the program evaluation and review technique uses DAGs to model the milestones and activities of large human projects, and schedule these projects to use as little total time as possible. Combinational logic blocks in electronic design, and the operations in dataflow programming languages. More abstractly, the reachability relation in a DAG forms a partial order, the corresponding concept for undirected graphs is a forest, an undirected graph without cycles. Choosing an orientation for a forest produces a kind of directed acyclic graph called a polytree. However there are other kinds of directed acyclic graph that are not formed by orienting the edges of an undirected acyclic graph. Moreover, every undirected graph has an orientation, an assignment of a direction for its edges that makes it into a directed acyclic graph. To emphasize that DAGs are not the thing as directed versions of undirected acyclic graphs. A graph is formed by a collection of vertices and edges, in the case of a directed graph, each edge has an orientation, from one vertex to another vertex. A directed acyclic graph is a graph that has no cycles. A vertex v of a graph is said to be reachable from another vertex u when there exists a path that starts at u. As a special case, every vertex is considered to be reachable from itself, a graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with an ordering is acyclic. Conversely, every directed acyclic graph has a topological ordering, therefore, this property can be used as an alternative definition of the directed acyclic graphs, they are exactly the graphs that have topological orderings. The reachability relationship in any directed graph can be formalized as a partial order ≤ on the vertices of the DAG. For example, the DAG with two edges a → b and b → c has the same reachability relation as the graph with three edges a → b, b → c, and a → c

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

11.
Graph minor
–
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagners theorem that a graph is planar if, the Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions. Important variants of graph minors include the topological minors and immersion minors, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices it used to connect. An undirected graph H is a minor of another undirected graph G if a graph isomorphic to H can be obtained from G by contracting edges, deleting some edges. The order in which a sequence of contractions and deletions is performed on G does not affect the resulting graph H. Graph minors are often studied in the more general context of matroid minors. In this context, it is common to assume that all graphs are connected, with self-loops and multiple edges allowed, the contraction of a loop and the deletion of a cut-edge are forbidden operations. This point of view has the advantage that edge deletions leave the rank of a graph unchanged, in other contexts it makes more sense to allow the deletion of a cut-edge, and to allow disconnected graphs, but to forbid multigraphs. In this variation of graph theory, a graph is always simplified after any edge contraction to eliminate its self-loops. In the following example, graph H is a minor of graph G, H. G, another equivalent way of stating this is that any set of graphs can have only a finite number of minimal elements under the minor ordering. This result proved a conjecture known as Wagners conjecture, after Klaus Wagner, Wagner had conjectured it long earlier. Thus, their theory establishes fundamental connections between graph minors and topological embeddings of graphs, for any graph H, the simple H-minor-free graphs must be sparse, which means that the number of edges is less than some constant multiple of the number of vertices. More specifically, if H has h vertices, then a simple n-vertex simple H-minor-free graph can have at most O edges, thus, if H has h vertices, then H-minor-free graphs have average degree O and furthermore degeneracy O. Even stronger, for any fixed H, H-minor-free graphs have treewidth O, the Hadwiger conjecture in graph theory proposes that if a graph G does not contain a minor isomorphic to the complete graph on k vertices, then G has a proper coloring with k −1 colors. The case k =5 is a restatement of the four color theorem, the Hadwiger conjecture has been proven for k ≤6, but is unknown in the general case. Bollobás, Catlin & Erdős call it “one of the deepest unsolved problems in graph theory. ”Many families of graphs have the property that every minor of a graph in F is also in F, such a class is said to be minor-closed. If F is a family, then among the graphs that do not belong to F there is a finite set X of minor-minimal graphs. These graphs are forbidden minors for F, a graph belongs to F if and that is, every minor-closed family F can be characterized as the family of X-minor-free graphs for some finite set X of forbidden minors. The best-known example of a characterization of this type is Wagners theorem characterizing the planar graphs as the graphs having neither K5 nor K3,3 as minors

12.
Degree (graph theory)
–
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a v is denoted deg ⁡ or deg ⁡ v. The maximum degree of a graph G, denoted by Δ, in the graph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, the degree sum formula states that, given a graph G =, ∑ v ∈ V deg ⁡ =2 | E |. The formula implies that in any graph, the number of vertices with odd degree is even and this statement is known as the handshaking lemma. The latter name comes from a mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even. The degree sequence of a graph is the non-increasing sequence of its vertex degrees. The degree sequence is a graph invariant so isomorphic graphs have the degree sequence. However, the sequence does not, in general, uniquely identify a graph, in some cases. The degree sequence problem is the problem of finding some or all graphs with the sequence being a given non-increasing sequence of positive integers. A sequence which is the sequence of some graph, i. e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the sum formula, any sequence with an odd sum, such as. The converse is true, if a sequence has an even sum. The construction of such a graph is straightforward, connect vertices with odd degrees in pairs by a matching, the question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm, the problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration. A vertex with degree 0 is called an isolated vertex, a vertex with degree 1 is called a leaf vertex or end vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, is a pendant edge and this terminology is common in the study of trees in graph theory and especially trees as data structures. A vertex with degree n −1 in a graph on n vertices is called a dominating vertex, if each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called …

All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E3 (red) admits a 1-coloring, the others admit no such colorings. The green graph admits 12 colorings with 3 colors.

A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.

A topological ordering of a directed acyclic graph: every edge goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.

A Hasse diagram representing the partial order of set inclusion (⊆) among the subsets of a three-element set.

In mathematics, the phrase up to appears in discussions about the elements of a set (say S), and the conditions under …

A solution of the eight queens problem

In a hexagon vertex set there are 20 partitions which have one three-element subset and three single-element subsets (uncolored) (top figure). Of these there are four partitions up to rotation, and three partitions up to rotation and reflection.