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

An edge (with ) is said to join the vertices and and is denoted by . One says that the edges and are equivalent; the vertices and are the endvertices of this edge. If , then and are adjacent, or neighboring, vertices of , and the vertices and are incident with the edge . Two edges are adjacent if they have at least one common endvertex. Also, means that the vertex is adjacent to the vertex .

Notice that this definition allows pairs of the form , 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.