Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Graph theory
Main Page | See live article | Alphabetical index

Graph theory

Graph theory is the branch of mathematics that examines the properties of graphs.
A graph with 6 vertices and 7 edges.

Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs). Typically, a graph is depicted as a set of dots (i.e., vertices) connected by lines (i.e., edges).

For more and formal definitions, see Glossary of graph theory and Graph (mathematics).

Depending on the applications, edges may or may not have a direction; edges joining a vertex to itself may or may not be allowed, and vertices and/or edges may be assigned weights, that is, numbers. If the edges have a direction associated with them (indicated by an arrow in the graphical representation) then it is a directed graph, or digraph.

A graph with only one vertex and no edges is the trivial graph or "the dot". A graph with only vertices and no edges is known as the empty graph, but is sometimes also known as the Null graph. See Glossary of graph theory.

Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be formulated as questions about certain graphs. Various networks are conveniently described by means of graphs. For example, the link structure of Wikipedia could be represented by a directed graph: the vertices are the articles in Wikipedia and there's a directed edge from article A to article B if and only if A contains a link to B. Directed graphs are also used to represent finite state machines. The development of algorithms to handle graphs is therefore of major interest in computer science.

Table of contents
1 History
2 Graph representations
3 Special graphs
4 Graph problems
5 Important algorithms
6 Generalizations
7 Related areas of mathematics
8 See also
9 External links


Leonhard Euler's paper on Seven Bridges of Königsberg; is considered to be the first result in graph theory. It is also regarded as one of the first topological results in geometry; that is, it does not depend on any measurements. This illustrates the deep connection between graph theory and topology.

Graph representations

In general, there are four ways to represent a graph in a computer system: The incidence list representation, the incidence matrix representation, adjacency list representation, and the adjacency matrix representation.

These two representations are most useful when information about the edges are more desirable than information about vertices. These two representations are most useful when information about the vertices is more desirable than information about the edges. These two representations are also most popular since information about the vertices is often more desirable than edges in most applications.

Special graphs

There are several kinds of special graphs, which have specific structures and properties:

Graph problems

Important algorithms


In a hypergraph, an edge can connect more than two vertices.

An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.

Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs.

In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number.

Related areas of mathematics

See also

External links

Topics in mathematics related to structure Edit
Abstract algebra | Number theory | Algebraic geometry | Group theory | Monoids | Analysis | Topology | Linear algebra | Graph theory | Universal algebra | Category theory | Order theory