graph

A graph $G$ is an ordered pair of disjoint sets $(V, E)$ such that $E$ is a subset of the set $V^{(2)}$ of unordered pairs of $V$ . $V$ and $E$ are always assumed to be finite, unless explicitly stated otherwise. The set $V$ is the set of vertices (sometimes called nodes) and $E$ is the set of edges. If $G$ is a graph, then $V = V(G)$ is the vertex set of $G$ , and $E = E(G)$ is the edge set. Typically, $V(G)$ is defined to be nonempty. If $x$ is a vertex of $G$ , we sometimes write $x \in G$ instead of $x \in V(G)$ .

An edge $\{x, y\}$ (with $x\neq y$ ) is said to join the vertices $x$ and $y$ and is denoted by $xy$ . One says that the edges $xy$ and $yx$ are equivalent; the vertices $x$ and $y$ are the endvertices of this edge. If $xy \in E(G)$ , then $x$ and $y$ are adjacent, or neighboring, vertices of $G$ , and the vertices $x$ and $y$ are incident with the edge $xy$ . Two edges are adjacent if they have at least one common endvertex. Also, $x \sim y$ means that the vertex $x$ is adjacent to the vertex $y$ .

Notice that this definition allows pairs of the form $\{x,x\}$ , which would correspond to a node joining to itself. Some authors explicitly disallow this in their definition of a graph.

                                 
Some graphs.

Note: Some authors include multigraphs in their definition of a graph. In this notation, the above definition corresponds to that of a simple graph. A graph is then simple if there is at most one edge joining each pair of nodes.

Adapted with permission of the author from Modern Graph Theory by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.