Definition and etymology
📜
The statement of the theorem
A graph consists of vertices connected by edges. A graph is occasionally called:
- An undirected graph (top left), distinguishing it from a directed graph that has an arrow on each edge (top right). Undirected and directed graphs can be merged into a mixed graph (bottom left); and
- A simple graph, distinguishing it from a multigraph (bottom right).
Graph theory is a branch of mathematics that studies graphs, a mathematical structure for modelling pairwise relations between objects. The term "graph" was introduced by James Joseph Sylvester in a paper published in 1878 in Nature, where he drew an analogy between "quantic invariants" and "co-variants" of algebra and molecular diagrams.
The definition of a graph can vary, but one can understand that a graph is a structure that contains the vertices (also called nodes or points) and edges (also called arcs, links, or lines). Two vertices of an edge are called the endpoints. Occasionally, a graph is called an undirected graph, to distinguish it from a directed graph. A directed graph is a graph where each edge has an assignment direction known as orientation, designated with an arrow. A mixed graph can have edges that may be directed, and some may be undirected. A graph can also be called a simple graph, to distinguish it from a multigraph. A multiple graph allows many edges to have the same pair of endpoints, and it also allows an edge connect a vertex to itself, known as a loop. A graph can have its edges assigned a number, which is known as the weight. Such a graph is called a weight graph.
- ^Sylvester (1878).
- ^Ore (1962), p. 1.
- ^Ore (1962), p. 2.
- ^Ore (1962), p. 3.
- ^Bollobas (2013), p. 7.