Graph

A set $V$ of vertices and a set $E$ of unordered and ordered pairs of vertices; denoted by $G(V,E)$. An unordered pair of vertices is said to be an edge, while an ordered pair is said to be an arc. A graph containing edges alone is said to be non-oriented or undirected; a graph containing arcs alone is said to be oriented or directed. A pair of vertices can be connected by two or more edges (arcs of the same direction) and such edges (arcs) are then said to be multiple. An arc (or edge) can begin and end at the same vertex, in which case it is known as a loop. (A "graph" is sometimes understood to be a graph without loops or multiple edges; in such a case a graph with multiple edges is said to be a multi-graph, whereas one containing both multiple edges and loops is said to be a pseudo-graph.)

Vertices connected by an edge or a loop are said to be adjacent. Edges with a common vertex are also called adjacent. An edge (arc) and any one of its two vertices are said to be incident. One says that an edge $\{u,v\}$ connects two vertices $u$ and $v$, while an arc $(u,v)$ begins at the vertex $u$ and ends at the vertex $v$. Each graph can be represented in Euclidean space by a set of points, corresponding to the vertices, which are connected by lines, corresponding to the edges (or the arcs) of the graph. In three-dimensional space any graph can be represented in such a way that the lines corresponding to edges (arcs) do not intersect at interior points.

There are various ways of specifying a graph. Let $u_1,\dots,u_n$ be the vertices of a graph $G(V,E)$ and let $e_1,\dots,e_m$ be its edges. The adjacency matrix corresponding to $G$ is the matrix $A=(a_{i,j})$ in which the element $a_{i,j}$ equals the number of edges (arcs) which join the vertices $u_i$ and $u_j$ (go from $u_i$ to $u_j$) and $a_{i,j}=0$ if the corresponding vertices are not adjacent. In the incidence matrix $B=(b_{i,j})$ of $G$ the element $b_{i,j}=1$ if the vertex $u_i$ is incident to the edge $e_j$, and $b_{i,j}=0$ if the vertex $u_i$ and the edge $e_j$ are not incident. A graph can be specified by lists, for example, by specifying pairs of vertices connected by edges (arcs) or by specifying the set of vertices adjacent to each vertex. Two graphs $G(V,E)$ and $H(W,I)$ are called isomorphic if there is a one-to-one correspondence between the sets of vertices $V,W$ and the sets of edges $E,I$ which preserves the incidence relationship (see also Graph isomorphism).

A subgraph $G'(V',E')$ of a graph $G(V,E)$ is defined as a graph with set of vertices $V'\subseteq V$ and set of edges (arcs) $E'\subseteq E$, each one of which is incident with vertices from $V'$ only. A subgraph $G'(V',E')$ is said to be generated or induced by the subset $V'\subseteq V$ if it is a graph with set of vertices $V'$ and ordered set of edges (arcs) $E'$, $E'$ consists of by all edges of $G$ which connect vertices of $V'$. A skeleton subgraph or spanning subgraph $G'(V,E')$ contains all vertices of $G$ and some subset of its edges (arcs) $E'\subseteq E$. A sequence of edges $(u_0,u_1),\dots,(u_{r-1},u_r)$ is called an edge progression or walk connecting the vertices $u_0$ and $u_r$. An edge progression is called a chain or trail if all its edges are different and a simple chain or path if all its vertices are different. A closed (simple) chain is also called a (simple) cycle. A graph is said to be connected if any pair of its vertices is connected by an edge progression. A maximal connected subgraph of a graph $G$ is said to be a connected component. A disconnected graph has at least two connected components (see also Graph, connectivity of a).

The length of an edge progression (chain, simple chain) is equal to the number of edges in the order in which they are traversed. The length of the shortest simple chain connecting two vertices $u_i$ and $u_j$ in a graph $G$ is said to be the distance $d(u_i,u_j)$ between $u_i$ and $u_j$. In a connected undirected graph the distance satisfies the axioms of a metric. The quantity $\min_{u_i} \max_{u_j} d(u_i,u_j)$ is called the diameter, while a vertex $u_0$ for which $\max_{u_j} d(u_i,u_j)$ assumes its minimum value is called a centre of $G$. A graph can contain more than one centre or no centre at all.

The degree of a vertex $u_i$ of a graph $G$, denoted by $d_i$, is the number of edges incident with that vertex. If a (loop-free) graph $G$ has $n$ vertices and $m$ edges, then $\sum_{i=1}^n d_i = 2m$. A vertex $u_i$ is said to be isolated if $d_i=0$ and terminal or pendant if $d_i=1$. A graph all vertices of which have the same degree (equal to $k$) is said to be regular of degree $k$. A complete graph has no loops and each pair of vertices is connected by exactly one edge. Let a graph $G(V,E)$ be free from loops or multiple edges; then the complementary graph to $G$ is the graph $\bar{G}(V,E)$ in which $\bar{V}=V$ and vertices are adjacent in $\bar{G}$ only if they are not adjacent in $G$. A graph which is complementary to a complete graph consists of isolated vertices and is known as empty. Many characteristics of a graph $G$ and of its complement $\bar{G}$ are related. In a directed graph $G$ one defines, for each vertex $u_i$, the output (or out) and the input (or in) (semi-) degree as the number of arcs issuing from and entering this vertex, respectively. A complete directed graph is known as a tournament. To each graph $G$ can be assigned a number of graphs which are derived from of $G$. Thus, the edge graph $L(G)$ of $G$ is the graph whose vertices correspond to the edges of $G$ and two vertices are adjacent in $L(G)$ if and only if the corresponding edges of $G$ are adjacent. In the total graph $T(G)$ of $G$ the vertices correspond to the elements of $G$, i.e. to vertices and edges, and two vertices in $T(G)$ are adjacent if and only if the corresponding elements in $G$ are adjacent or incident. Many properties of $G$ carry over to $L(G)$ and $T(G)$. Many generalizations of the concept of a "graph" are known, including that of a hypergraph and of a network graph.

With the aid of suitable operations it is possible to construct a graph from simpler graphs, to pass from a graph to simpler ones, to subdivide a graph into simpler ones, to pass from one graph to another in a given class of graphs, etc. The most common one-place operations include the removal of an edge (the vertices of the edge are preserved), the addition of an edge between two vertices of a graph, the removal of a vertex together with its incident edges (the graph obtained by removal of a vertex $v$ from a graph $G$ is often denoted by $G-v$), the addition of a vertex (which may be connected by edges with certain vertices of the graph), the contraction of an edge — identification of a pair of adjacent vertices, i.e. removal of a pair of adjacent vertices and addition of a new vertex which is adjacent to those vertices of the graph which were adjacent to at least one of the vertices which have been removed, and subdivision of an edge — removal of an edge and addition of a new vertex which is joined by an edge to each vertex of the edge which has been removed.

Two-place operations over a graph are employed in a number of problems in graph theory. Let $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ be graphs such that $V_1 \cap V_2 = \emptyset$ and $E_1 \cap E_2 = \emptyset$. The union of $G_1$ and $G_2$ is the graph $G = G_1 \cup G_2$ with set of vertices $V = V_1 \cup V_2$ and set of edges $E = E_1 \cup E_2$. The product of $G_1$ and $G_2$ is the graph $G = G_1 \times G_2$ whose set of vertices is the Cartesian product $V = V_1 \times V_2$, any two of the vertices $(u_1,u_2)$ and $(v_1,v_2)$ being adjacent if and only if either $u_1=v_1$ and $u_2$ is adjacent to $v_2$, or $u_2=v_2$ and $u_1$ is adjacent to $v_1$. For example, any graph is the union of its connected components; a graph known as the $n$-dimensional unit cube $Q_n$ can be recursively defined by the product operation

$$Q_n = K_2 \times Q_{n-2}$$

where $Q_1=K_2$ is the graph consisting of a pair of vertices connected by one edge. These operations can also be defined for intersecting graphs, in particular for subgraphs of a given graph. The addition modulo $2$ of two graphs $G_1$ and $G_2$ is defined as the graph $G$ with set of vertices $V = V_1 \cup V_2$ and set of edges $E = (E_1 \cup E_2) \setminus (E_1 \cap E_2)$. Other many-place operations on graphs are also employed.

For certain classes of graphs it is possible to find simple operations, a repeated application of which makes it possible to pass from any graph in the given class to any other graph in the same class. With the aid of the operation shown in Fig. A it is possible to pass from any graph to any other graph within the class of graphs with the same set of degrees.

Figure A

The operation shown in Fig. B makes it possible to pass from any triangulation to any other triangulation within the class of planar triangulations (cf. Graph, planar).

Figure B

The description and study of certain classes of graphs also involves operations and sets of graphs making it possible to obtain any graph of a given class. Operations on graphs are also employed to construct graphs with given properties, to calculate numerical characteristics of graphs, etc. (cf. Graph, numerical characteristics of a).

The concept of a "graph" is employed in defining mathematical ideas such as a control system, in certain definitions of an algorithm, of a grammar, etc. The exposition of a number of mathematical theories becomes more easily understood if geometric representations of graphs are employed, e.g. the theory of Markov chains. The concept of a "graph" is widely employed in the formulation and description of various mathematical models in economics, biology, etc.

References

[1]	C. Berge, "The theory of graphs and their applications" , Wiley (1962) (Translated from French)
[2]	O. Ore, "Theory of graphs" , Amer. Math. Soc. (1962)
[3]	A.A. Zykov, "The theory of finite graphs" , 1 , Novosibirsk (1969) (In Russian)
[4]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9

Comments

There is as yet no universally accepted terminology in graph theory. In the English literature there are basically three schools of terminology: the French school typified by Berge's books [1] and [a1], the Canadian school typified by the books [a2] and [a3] and the American (especially Michigan) school typified by the books [4] and [a4]. Some of the terminology used in the present article differ from all these.

References

[a1]	C. Berge, "Graphs and hypergraphs" , North-Holland (1973) (Translated from French)
[a2]	J.A. Bondy, U.S.R. Murthy, "Graph theory with applications" , Macmillan (1976)
[a3]	W.T. Tutte, "Graph theory" , Addison-Wesley (1984)
[a4]	M. Behzad, G. Chartrand, L.L. Foster, "Graphs and digraphs" , Prindle, Weber & Schmidt (1979)
[a5]	R.J. Wilson, "Introduction to graph theory" , Longman (1985)