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∈G instead of x∈V(G).
An edge {x,y} (with x≠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∈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∼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.
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.