Graph theory

Abstract

A graph is a set of points (commonly called vertices or nodes) in space that are interconnected by a set of lines (called edges). For a graph G, the edge set is denoted by E and the vertex set by V, so that G= (V, E). Common nomenclature denotes the number of vertices |V| by n and the number of edges |E| by m. Fig. 1 shows a graph G with V= {v1, v2, v3, v4, v5}, E = {e1, e2, e3, e4, e5, e6, e7}, n = 5, and m = 7. If, within E, each edge is specified by its pair of endpoints (e.g. for the example of Fig. 1, e1 is replaced by (v1, v2) etc.), the figure can be dispensed with.