Chapter 1 - Basic concepts

Summary

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 d_G(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.