
In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, graph theory is the study of ''
graphs'', which are
mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''
vertices'' (also called ''nodes'' or ''points'') which are connected by ''
edges'' (also called ''arcs'', ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in
discrete mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
.
Definitions
Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related
mathematical structure
In mathematics, a structure on a set (or on some sets) refers to providing or endowing it (or them) with certain additional features (e.g. an operation, relation, metric, or topology). Τhe additional features are attached or related to the ...
s.
Graph

In one restricted but very common sense of the term, a graph is an
ordered pair comprising:
*
, a
set of vertices (also called nodes or points);
*
, a
set of edges (also called links or lines), which are
unordered pairs of vertices (that is, an edge is associated with two distinct vertices).
To avoid ambiguity, this type of object may be called an undirected simple graph.
In the edge
, the vertices
and
are called the endpoints of the edge. The edge is said to join
and
and to be incident on
and on
. A vertex may exist in a graph and not belong to an edge. Under this definition,
multiple edges
In graph theory, multiple edges (also called parallel edges or a multi-edge), are, in an undirected graph, two or more edges that are incident to the same two vertices, or in a directed graph, two or more edges with both the same tail verte ...
, in which two or more edges connect the same vertices, are not allowed.

In one more general sense of the term allowing multiple edges, a graph is an ordered triple
comprising:
*
, a
set of vertices (also called nodes or points);
*
, a
set of edges (also called links or lines);
*
, an incidence function mapping every edge to an
unordered pair of vertices (that is, an edge is associated with two distinct vertices).
To avoid ambiguity, this type of object may be called an undirected
multigraph.
A
loop is an edge that joins a vertex to itself. Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex
to itself is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph)
which is not in
. To allow loops, the definitions must be expanded. For undirected simple graphs, the definition of
should be modified to
. For undirected multigraphs, the definition of
should be modified to
. To avoid ambiguity, these types of objects may be called undirected simple graph permitting loops and undirected multigraph permitting loops (sometimes also undirected
pseudograph
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mo ...
), respectively.
and
are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the
infinite case. Moreover,
is often assumed to be non-empty, but
is allowed to be the empty set. The order of a graph is
, its number of vertices. The size of a graph is
, its number of edges. The degree or valency of a vertex is the number of edges that are incident to it, where a loop is counted twice. The degree of a graph is the maximum of the degrees of its vertices.
In an undirected simple graph of order ''n'', the maximum degree of each vertex is and the maximum size of the graph is .
The edges of an undirected simple graph permitting loops
induce a symmetric
homogeneous relation on the vertices of
that is called the adjacency relation of
. Specifically, for each edge
, its endpoints
and
are said to be adjacent to one another, which is denoted
.
Directed graph

A directed graph or digraph is a graph in which edges have orientations.
In one restricted but very common sense of the term, a directed graph is an ordered pair
comprising:
*
, a
set of ''vertices'' (also called ''nodes'' or ''points'');
*
, a
set of ''edges'' (also called ''directed edges'', ''directed links'', ''directed lines'', ''arrows'' or ''arcs'') which are
ordered pairs of vertices (that is, an edge is associated with two distinct vertices).
To avoid ambiguity, this type of object may be called a directed simple graph. In set theory and graph theory,
denotes the set of -
tuple
In mathematics, a tuple is a finite sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...
s of elements of
that is, ordered sequences of
elements that are not necessarily distinct.
In the edge
directed from
to
, the vertices
and
are called the ''endpoints'' of the edge,
the ''tail'' of the edge and
the ''head'' of the edge. The edge is said to ''join''
and
and to be ''incident'' on
and on
. A vertex may exist in a graph and not belong to an edge. The edge
is called the ''inverted edge'' of
. ''
Multiple edges
In graph theory, multiple edges (also called parallel edges or a multi-edge), are, in an undirected graph, two or more edges that are incident to the same two vertices, or in a directed graph, two or more edges with both the same tail verte ...
'', not allowed under the definition above, are two or more edges with both the same tail and the same head.
In one more general sense of the term allowing multiple edges, a directed graph is an ordered triple
comprising:
*
, a
set of ''vertices'' (also called ''nodes'' or ''points'');
*
, a
set of ''edges'' (also called ''directed edges'', ''directed links'', ''directed lines'', ''arrows'' or ''arcs'');
*
, an ''incidence function'' mapping every edge to an
ordered pair of vertices (that is, an edge is associated with two distinct vertices).
To avoid ambiguity, this type of object may be called a directed multigraph.
A ''
loop'' is an edge that joins a vertex to itself. Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex
to itself is the edge (for a directed simple graph) or is incident on (for a directed multigraph)
which is not in
. So to allow loops the definitions must be expanded. For directed simple graphs, the definition of
should be modified to
. For directed multigraphs, the definition of
should be modified to
. To avoid ambiguity, these types of objects may be called precisely a directed simple graph permitting loops and a directed multigraph permitting loops (or a ''
quiver'') respectively.
The edges of a directed simple graph permitting loops
is a
homogeneous relation ~ on the vertices of
that is called the ''adjacency relation'' of
. Specifically, for each edge
, its endpoints
and
are said to be ''adjacent'' to one another, which is denoted
~
.
Applications

Graphs can be used to model many types of relations and processes in physical, biological, social and information systems. Many practical problems can be represented by graphs. Emphasizing their application to real-world systems, the term ''network'' is sometimes defined to mean a graph in which attributes (e.g. names) are associated with the vertices and edges, and the subject that expresses and understands real-world systems as a network is called
network science
Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, Cognitive network, cognitive and semantic networks, and social networks, considering distinct eleme ...
.
Computer science
Within
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, '
causal' and 'non-causal' linked structures are graphs that are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a
website
A website (also written as a web site) is any web page whose content is identified by a common domain name and is published on at least one web server. Websites are typically dedicated to a particular topic or purpose, such as news, educatio ...
can be represented by a directed graph, in which the vertices represent web pages and directed edges represent
links from one page to another. A similar approach can be taken to problems in social media, travel, biology, computer chip design, mapping the progression of neuro-degenerative diseases, and many other fields. The development of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s to
handle graphs is therefore of major interest in computer science. The
transformation of graphs is often formalized and represented by
graph rewrite systems. Complementary to
graph transformation systems focusing on rule-based in-memory manipulation of graphs are
graph databases geared towards
transaction-safe,
persistent storing and querying of
graph-structured data.
Linguistics
Graph-theoretic methods, in various forms, have proven particularly useful in
linguistics
Linguistics is the scientific study of language. The areas of linguistic analysis are syntax (rules governing the structure of sentences), semantics (meaning), Morphology (linguistics), morphology (structure of words), phonetics (speech sounds ...
, since natural language often lends itself well to discrete structure. Traditionally,
syntax
In linguistics, syntax ( ) is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure (constituenc ...
and compositional semantics follow tree-based structures, whose expressive power lies in the
principle of compositionality, modeled in a hierarchical graph. More contemporary approaches such as
head-driven phrase structure grammar
Head-driven phrase structure grammar (HPSG) is a highly lexicalized, constraint-based grammar
developed by Carl Pollard and Ivan Sag. It is a type of phrase structure grammar, as opposed to a dependency grammar, and it is the immediate successor t ...
model the syntax of natural language using
typed feature structures, which are
directed acyclic graphs.
Within
lexical semantics, especially as applied to computers, modeling word meaning is easier when a given word is understood in terms of related words;
semantic networks are therefore important in
computational linguistics. Still, other methods in phonology (e.g.
optimality theory, which uses
lattice graphs) and morphology (e.g. finite-state morphology, using
finite-state transducers) are common in the analysis of language as a graph. Indeed, the usefulness of this area of mathematics to linguistics has borne organizations such a
TextGraphs as well as various 'Net' projects, such as
WordNet
WordNet is a lexical database of semantic relations between words that links words into semantic relations including synonyms, hyponyms, and meronyms. The synonyms are grouped into ''synsets'' with short definitions and usage examples. It can thu ...
,
VerbNet, and others.
Physics and chemistry
Graph theory is also used to study molecules in
chemistry
Chemistry is the scientific study of the properties and behavior of matter. It is a physical science within the natural sciences that studies the chemical elements that make up matter and chemical compound, compounds made of atoms, molecules a ...
and
physics
Physics is the scientific study of matter, its Elementary particle, fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge whi ...
. In
condensed matter physics
Condensed matter physics is the field of physics that deals with the macroscopic and microscopic physical properties of matter, especially the solid and liquid State of matter, phases, that arise from electromagnetic forces between atoms and elec ...
, the three-dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. Also, "the
Feynman graphs and rules of calculation summarize
quantum field theory
In theoretical physics, quantum field theory (QFT) is a theoretical framework that combines Field theory (physics), field theory and the principle of relativity with ideas behind quantum mechanics. QFT is used in particle physics to construct phy ...
in a form in close contact with the experimental numbers one wants to understand." In chemistry a graph makes a natural model for a molecule, where vertices represent
atom
Atoms are the basic particles of the chemical elements. An atom consists of a atomic nucleus, nucleus of protons and generally neutrons, surrounded by an electromagnetically bound swarm of electrons. The chemical elements are distinguished fr ...
s and edges
bonds. This approach is especially used in computer processing of molecular structures, ranging from
chemical editors to database searching. In
statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such
systems. Similarly, in
computational neuroscience graphs can be used to represent functional connections between brain areas that interact to give rise to various cognitive processes, where the vertices represent different areas of the brain and the edges represent the connections between those areas. Graph theory plays an important role in electrical modeling of electrical networks, here, weights are associated with resistance of the wire segments to obtain electrical properties of network structures. Graphs are also used to represent the micro-scale channels of
porous media, in which the vertices represent the pores and the edges represent the smaller channels connecting the pores.
Chemical graph theory uses the
molecular graph as a means to model molecules.
Graphs and networks are excellent models to study and understand phase transitions and critical phenomena.
Removal of nodes or edges leads to a critical transition where the network breaks into small clusters which is studied as a phase transition. This breakdown is studied via
percolation theory.
Social sciences

Graph theory is also widely used in
sociology
Sociology is the scientific study of human society that focuses on society, human social behavior, patterns of Interpersonal ties, social relationships, social interaction, and aspects of culture associated with everyday life. The term sociol ...
as a way, for example, to
measure actors' prestige or to explore
rumor spreading, notably through the use of
social network analysis
Social network analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It characterizes networked structures in terms of ''nodes'' (individual actors, people, or things within the network) ...
software. Under the umbrella of social networks are many different types of graphs. Acquaintanceship and friendship graphs describe whether people know each other. Influence graphs model whether certain people can influence the behavior of others. Finally, collaboration graphs model whether two people work together in a particular way, such as acting in a movie together.
Biology
Likewise, graph theory is useful in
biology
Biology is the scientific study of life and living organisms. It is a broad natural science that encompasses a wide range of fields and unifying principles that explain the structure, function, growth, History of life, origin, evolution, and ...
and conservation efforts where a vertex can represent regions where certain species exist (or inhabit) and the edges represent migration paths or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.
Graphs are also commonly used in
molecular biology
Molecular biology is a branch of biology that seeks to understand the molecule, molecular basis of biological activity in and between Cell (biology), cells, including biomolecule, biomolecular synthesis, modification, mechanisms, and interactio ...
and
genomics to model and analyse datasets with complex relationships. For example, graph-based methods are often used to 'cluster' cells together into cell-types in
single-cell transcriptome analysis. Another use is to model genes or proteins in a
pathway and study the relationships between them, such as metabolic pathways and gene regulatory networks. Evolutionary trees, ecological networks, and hierarchical clustering of gene expression patterns are also represented as graph structures.
Graph theory is also used in
connectomics; nervous systems can be seen as a graph, where the nodes are neurons and the edges are the connections between them.
Mathematics
In mathematics, graphs are useful in geometry and certain parts of
topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
such as
knot theory
In topology, knot theory is the study of knot (mathematics), mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be und ...
.
Algebraic graph theory has close links with
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...
. Algebraic graph theory has been applied to many areas including dynamic systems and complexity.
Other topics
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or
weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example, if a graph represents a road network, the weights could represent the length of each road. There may be several weights associated with each edge, including distance (as in the previous example), travel time, or monetary cost. Such weighted graphs are commonly used to program GPS's, and travel-planning search engines that compare flight times and costs.
History

The paper written by
Leonhard Euler
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
on the
Seven Bridges of Königsberg and published in 1736 is regarded as the first paper in the history of graph theory.
This paper, as well as the one written by
Vandermonde on the ''
knight problem,'' carried on with the ''analysis situs'' initiated by
Leibniz. Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by
Cauchy and
L'Huilier,
and represents the beginning of the branch of mathematics known as
topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
.
More than one century after Euler's paper on the bridges of
Königsberg
Königsberg (; ; ; ; ; ; , ) is the historic Germany, German and Prussian name of the city now called Kaliningrad, Russia. The city was founded in 1255 on the site of the small Old Prussians, Old Prussian settlement ''Twangste'' by the Teuton ...
and while
Listing was introducing the concept of topology,
Cayley was led by an interest in particular analytical forms arising from
differential calculus
In mathematics, differential calculus is a subfield of calculus that studies the rates at which quantities change. It is one of the two traditional divisions of calculus, the other being integral calculus—the study of the area beneath a curve. ...
to study a particular class of graphs, the ''
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
s''. This study had many implications for theoretical
chemistry
Chemistry is the scientific study of the properties and behavior of matter. It is a physical science within the natural sciences that studies the chemical elements that make up matter and chemical compound, compounds made of atoms, molecules a ...
. The techniques he used mainly concern the
enumeration of graphs with particular properties. Enumerative graph theory then arose from the results of Cayley and the fundamental results published by
Pólya between 1935 and 1937. These were generalized by
De Bruijn in 1959. Cayley linked his results on trees with contemporary studies of chemical composition.
The fusion of ideas from mathematics with those from chemistry began what has become part of the standard terminology of graph theory.
In particular, the term "graph" was introduced by
Sylvester
Sylvester or Silvester is a name derived from the Latin adjective ''silvestris'' meaning "wooded" or "wild", which derives from the noun ''silva'' meaning "woodland". Classical Latin spells this with ''i''. In Classical Latin, ''y'' represented a ...
in a paper published in 1878 in ''
Nature
Nature is an inherent character or constitution, particularly of the Ecosphere (planetary), ecosphere or the universe as a whole. In this general sense nature refers to the Scientific law, laws, elements and phenomenon, phenomena of the physic ...
'', where he draws an analogy between "quantic invariants" and "co-variants" of algebra and molecular diagrams:
:"
��Every invariant and co-variant thus becomes expressible by a ''graph'' precisely identical with a
Kekuléan diagram or chemicograph.
��I give a rule for the geometrical multiplication of graphs, ''i.e.'' for constructing a ''graph'' to the product of in- or co-variants whose separate graphs are given.
�� (italics as in the original).
The first textbook on graph theory was written by
Dénes Kőnig, and published in 1936. Another book by
Frank Harary, published in 1969, was "considered the world over to be the definitive textbook on the subject", and enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other. Harary donated all of the royalties to fund the
Pólya Prize.
One of the most famous and stimulating problems in graph theory is the
four color problem: "Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?" This problem was first posed by
Francis Guthrie in 1852 and its first written record is in a letter of
De Morgan addressed to
Hamilton the same year. Many incorrect proofs have been proposed, including those by Cayley,
Kempe, and others. The study and the generalization of this problem by
Tait,
Heawood,
Ramsey and
Hadwiger led to the study of the colorings of the graphs embedded on surfaces with arbitrary
genus
Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...
. Tait's reformulation generated a new class of problems, the ''factorization problems'', particularly studied by
Petersen and
Kőnig. The works of Ramsey on colorations and more specially the results obtained by
Turán in 1941 was at the origin of another branch of graph theory, ''
extremal graph theory''.
The four color problem remained unsolved for more than a century. In 1969
Heinrich Heesch published a method for solving the problem using computers. A computer-aided proof produced in 1976 by
Kenneth Appel and
Wolfgang Haken makes fundamental use of the notion of "discharging" developed by Heesch.
The proof involved checking the properties of 1,936 configurations by computer, and was not fully accepted at the time due to its complexity. A simpler proof considering only 633 configurations was given twenty years later by
Robertson,
Seymour,
Sanders and
Thomas.
The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of
Jordan
Jordan, officially the Hashemite Kingdom of Jordan, is a country in the Southern Levant region of West Asia. Jordan is bordered by Syria to the north, Iraq to the east, Saudi Arabia to the south, and Israel and the occupied Palestinian ter ...
,
Kuratowski and
Whitney. Another important factor of common development of graph theory and
topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
came from the use of the techniques of modern algebra. The first example of such a use comes from the work of the physicist
Gustav Kirchhoff, who published in 1845 his
Kirchhoff's circuit laws for calculating the
voltage
Voltage, also known as (electrical) potential difference, electric pressure, or electric tension, is the difference in electric potential between two points. In a Electrostatics, static electric field, it corresponds to the Work (electrical), ...
and
current in
electric circuit
An electrical network is an interconnection of electrical components (e.g., battery (electricity), batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e. ...
s.
The introduction of probabilistic methods in graph theory, especially in the study of
Erdős and
Rényi of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as ''
random graph theory'', which has been a fruitful source of graph-theoretic results.
Representation
A graph is an abstraction of relationships that emerge in nature; hence, it cannot be coupled to a certain representation. The way it is represented depends on the degree of convenience such representation provides for a certain application. The most common representations are the visual, in which, usually, vertices are drawn and connected by edges, and the tabular, in which rows of a table provide information about the relationships between the vertices within the graph.
Visual: Graph drawing
Graphs are usually represented visually by drawing a point or circle for every vertex, and drawing a line between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow. If the graph is weighted, the weight is added on the arrow.
A graph drawing should not be confused with the graph itself (the abstract, non-visual structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice, it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.
The pioneering work of
W. T. Tutte was very influential on the subject of graph drawing. Among other achievements, he introduced the use of linear algebraic methods to obtain graph drawings.
Graph drawing also can be said to encompass problems that deal with the
crossing number and its various generalizations. The crossing number of a graph is the minimum number of intersections between edges that a drawing of the graph in the plane must contain. For a
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
, the crossing number is zero by definition. Drawings on surfaces other than the plane are also studied.
There are other techniques to visualize a graph away from vertices and edges, including
circle packings,
intersection graph, and other visualizations of the
adjacency matrix.
Tabular: Graph data structures
The tabular representation lends itself well to computational applications. There are different ways to store graphs in a computer system. The
data structure
In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
used depends on both the graph structure and the
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for
sparse graph
In mathematics, a dense graph is a Graph (discrete mathematics), graph in which the number of edges is close to the maximal number of edges (where every pair of Vertex (graph theory), vertices is connected by one edge). The opposite, a graph with ...
s as they have smaller memory requirements.
Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory. Implementations of sparse matrix structures that are efficient on modern parallel computer architectures are an object of current investigation.
List structures include the
edge list, an array of pairs of vertices, and the
adjacency list, which separately lists the neighbors of each vertex: Much like the edge list, each vertex has a list of which vertices it is adjacent to.
Matrix structures include the
incidence matrix, a matrix of 0's and 1's whose rows represent vertices and whose columns represent edges, and the
adjacency matrix, in which both the rows and columns are indexed by vertices. In both cases a 1 indicates two adjacent objects and a 0 indicates two non-adjacent objects. The
degree matrix indicates the degree of vertices. The
Laplacian matrix is a modified form of the adjacency matrix that incorporates information about the
degrees of the vertices, and is useful in some calculations such as
Kirchhoff's theorem on the number of
spanning trees of a graph.
The
distance matrix, like the adjacency matrix, has both its rows and columns indexed by vertices, but rather than containing a 0 or a 1 in each cell it contains the length of a
shortest path between two vertices.
Problems
Enumeration
There is a large literature on
graphical enumeration: the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973).
Subgraphs, induced subgraphs, and minors
A common problem, called the
subgraph isomorphism problem, is finding a fixed graph as a
subgraph in a given graph. One reason to be interested in such a question is that many
graph properties are ''hereditary'' for subgraphs, which means that a graph has the property if and only if all subgraphs have it too.
Finding maximal subgraphs of a certain kind is often an
NP-complete problem. For example:
* Finding the largest complete subgraph is called the
clique problem (NP-complete).
One special case of subgraph isomorphism is the
graph isomorphism problem. It asks whether two graphs are isomorphic. It is not known whether this problem is NP-complete, nor whether it can be solved in polynomial time.
A similar problem is finding
induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example:
* Finding the largest edgeless induced subgraph or
independent set is called the
independent set problem (NP-complete).
Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A
minor or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. For example,
Wagner's Theorem states:
* A graph is
planar if it contains as a minor neither the
complete bipartite graph ''K''
3,3 (see the
Three-cottage problem) nor the complete graph ''K''
5.
A similar problem, the subdivision containment problem, is to find a fixed graph as a
subdivision of a given graph. A
subdivision or
homeomorphism
In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function ...
of a graph is any graph obtained by subdividing some (or no) edges. Subdivision containment is related to graph properties such as
planarity. For example,
Kuratowski's Theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a Glossary of graph theory#Su ...
states:
* A graph is
planar if it contains as a subdivision neither the
complete bipartite graph ''K''
3,3 nor the
complete graph ''K''
5.
Another problem in subdivision containment is the
Kelmans–Seymour conjecture:
* Every
5-vertex-connected graph that is not
planar contains a
subdivision of the 5-vertex
complete graph ''K''
5.
Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their ''point-deleted subgraphs''. For example:
* The
reconstruction conjecture
Graph coloring
Many problems and theorems in graph theory have to do with various ways of coloring graphs. Typically, one is interested in coloring a graph so that no two adjacent vertices have the same color, or with other similar restrictions. One may also consider coloring edges (possibly so that no two coincident edges are the same color), or other variations. Among the famous results and conjectures concerning graph coloring are the following:
*
Four-color theorem
*
Strong perfect graph theorem
*
Erdős–Faber–Lovász conjecture
*
Total coloring conjecture, also called
Behzad's conjecture (unsolved)
*
List coloring conjecture (unsolved)
*
Hadwiger conjecture (graph theory) (unsolved)
Subsumption and unification
Constraint modeling theories concern families of directed graphs related by a
partial order. In these applications, graphs are ordered by specificity, meaning that more constrained graphs—which are more specific and thus contain a greater amount of information—are subsumed by those that are more general. Operations between graphs include evaluating the direction of a subsumption relationship between two graphs, if any, and computing graph unification. The unification of two argument graphs is defined as the most general graph (or the computation thereof) that is consistent with (i.e. contains all of the information in) the inputs, if such a graph exists; efficient unification algorithms are known.
For constraint frameworks which are strictly
compositional, graph unification is the sufficient satisfiability and combination function. Well-known applications include
automatic theorem proving and modeling the
elaboration of linguistic structure.
Route problems
*
Hamiltonian path problem
*
Minimum spanning tree
*
Route inspection problem
In graph theory and combinatorial optimization, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at ...
(also called the "Chinese postman problem")
*
Seven bridges of Königsberg
*
Shortest path problem
*
Steiner tree
*
Three-cottage problem
*
Traveling salesman problem (NP-hard)
Network flow
There are numerous problems arising especially from applications that have to do with various notions of
flows in networks, for example:
*
Max flow min cut theorem
Visibility problems
*
Museum guard problem
Covering problems
Covering problems in graphs may refer to various
set cover problems on subsets of vertices/subgraphs.
*
Dominating set problem is the special case of set cover problem where sets are the closed
neighborhoods.
*
Vertex cover problem is the special case of set cover problem where sets to cover are every edges.
* The original set cover problem, also called hitting set, can be described as a vertex cover in a hypergraph.
Decomposition problems
Decomposition, defined as partitioning the edge set of a graph (with as many vertices as necessary accompanying the edges of each part of the partition), has a wide variety of questions. Often, the problem is to decompose a graph into subgraphs isomorphic to a fixed graph; for instance, decomposing a complete graph into Hamiltonian cycles. Other problems specify a family of graphs into which a given graph should be decomposed, for instance, a family of cycles, or decomposing a complete graph ''K''
''n'' into specified trees having, respectively, 1, 2, 3, ..., edges.
Some specific decomposition problems and similar problems that have been studied include:
*
Arboricity, a decomposition into as few forests as possible
*
Cycle double cover, a collection of cycles covering each edge exactly twice
*
Edge coloring, a decomposition into as few
matchings as possible
*
Graph factorization, a decomposition of a
regular graph into regular subgraphs of given degrees
Graph classes
Many problems involve characterizing the members of various classes of graphs. Some examples of such questions are below:
*
Enumerating the members of a class
* Characterizing a class in terms of
forbidden substructures
* Ascertaining relationships among classes (e.g. does one property of graphs imply another)
* Finding efficient
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s to
decide membership in a class
* Finding
representations for members of a class
See also
*
Gallery of named graphs
*
Glossary of graph theory
*
List of graph theory topics
*
List of unsolved problems in graph theory
*
Publications in graph theory
*
Graph algorithm
*
Graph theorists
Subareas
*
Algebraic graph theory
*
Geometric graph theory
*
Extremal graph theory
*
Probabilistic graph theory
*
Topological graph theory
*
Graph drawing
Notes
References
* Lowell W. Beineke; Bjarne Toft; and Robin J. Wilson: ''Milestones in Graph Theory: A Century of Progress'', AMS/MAA, (SPECTRUM, v.108), ISBN 978-1-4704-6431-8 (2025).
*
* English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
*
*
*
*
*
*
*
*
*
*
*
*
External links
*
Graph theory tutorial
A searchable database of small connected graphsHouse of Graphs— searchable database of graphs with a drawing-based search feature.
*
*
rocs— a graph theory IDE
The Social Life of Routers— non-technical paper discussing graphs of people and computers
Graph Theory Software— tools to teach and learn graph theory
*
with references and links to graph library implementations
Online textbooks
Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs(2006) by Hartmann and Weigt
Digraphs: Theory Algorithms and Applications2007 by Jorgen Bang-Jensen and Gregory Gutin
{{DEFAULTSORT:Graph Theory