Graphs

In this opening chapter it is our intention to give the basic definitions and some of the notation which we shall use throughout this book. We begin with some basic concepts concerning graphs.

A graph is an ordered triple (V(G), E(G), ψG) consisting of a finite, non-empty set of vertices, V(G), a finite set E(G) of edges, disjoint from V(G), and an incidence function ψG that associates an unordered pair of distinct vertices with each edge. We say that e joins u and v if ψG(e) = {u, v}, written uv, and that e has ends u and v. An edge is incident with a vertex v if v is one of its ends, and two vertices joined by an edge are adjacent. Edges which have the same ends are called multiple or parallel edges: the case when an edge joins a vertex to itself will not be considered in this book. We shall call a graph with no multiple edges simple. If G is simple and e ∈ E(G) an edge with ψG(e) = uv, we shall write e = uv. The degree dG(v) of a vertex v is the number of edges incident with v. We denote the minimum and maximum degrees of G by δ(G) and Δ(G), respectively. A vertex with degree zero is called an isolated vertex.