ABSTRACT
A graph is a data structure comprising a set V of vertices and a set E of edges, each edge corresponding to a pair of vertices called its endpoints. The number of vertices is denoted n, and the number of edges is denoted m. An edge is incident to its endpoints, and the degree of a vertex is the number of edges incident to the vertex. A walk is a sequence of vertices (v0, v1, . . ., vk) and the edges (vi−1, vi) for 0 < i ≤ k. A path is a walk with no repeated vertex. A cycle is a walk with no repeated vertex except v0 = vk. A vertex v is adjacent to a vertex w, and has w as a neighbor , if there exists an edge (v, w) in E that associates v with w. A graph is connected if, for every pair of vertices u and v, there exists a path from u to
Figure 21.1 (a) Nonplanar embedding of K4 and (b) planar embedding of K4.
