Introduction to Graph Theory

Author: B. Bollobas
Publisher:
Publish Date: 1999-11-01
Features: This book is intended for the young student who is interested in graph theory and wishes to study it as part of his mathematical education. Experience at Cambridge shows that none of the currently available texts meet this need. Either they are too specialized for their audience or they lack the depth and development needed to reveal the nature of the subject. This book is in English. Excerpt:
CHAPTER 1 Fundamentals
The purpose of this introduction is to familiarize the reader with the basic concepts and results of graph theory. The chapter inevitably contains a large number of definitions, and in order to prevent the reader growing weary, we prove simple results as soon as possible. The reader is not expected to have complete mastery of Chapter 1 before sampling the rest of the book, indeed, he is encouraged to skip ahead since most of the terminology is self-explanatory. We should add at this stage that the terminology of graph theory is far from being standard, though that used in this book is well accepted.
Definitions
A graph G is an ordered pair of disjoint sets (V, E) such that E is a subset of the set of unordered pairs of V. Unless it is explicitly stated otherwise, we consider only finite graphs, that is, V and E are always finite. The set V is the set of vertices 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. An edge {x, y} is said to join the vertices x and y and is denoted by xy. Thus xy and yx mean exactly the same edge; the vertices x and y are the end vertices of this edge. If xy ∈ E(G), then x and y are adjacent or neighbouring vertices of G and the vertices x and y are incident with the edge xy. Two edges are adjacent if they have exactly one common end vertex. As the terminology suggests, we do not usually think of a graph as an ordered pair, but as a collection of vertices some of which are joined by edges. It is then a natural step to draw a picture of the graph. In fact, sometimes the easiest way to describe a graph is to draw it; the graph G = ({1, 2, 3, 4, 5, 6}, {12, 14, 16, 25, 34, 36, 45, 56}) is immediately comprehended by looking at Figure 1.1. We say that G' = (V', E') is a subgraph of G = (V, E) if V' ? V and E' ? E. In this case we write G' ? G. If G' contains all the edges of G that join two vertices in V', then G' is said to be the subgraph induced or spanned by V' and is denoted by G[V']. A subgraph G' of G is an induced subgraph if G' = G[G']. If V' = V, then G' is said to be a spanning subgraph of G. These concepts are illustrated in Figure 1.2. We shall often construct new graphs from old ones by deleting or adding some vertices and edges. If W ? V(G), then G - W = G[V \ W] is the subgraph of G obtained by deleting the vertices in W and all edges incident with them. Similarly, if E' ? E(G), then G - E' = (V(G), E(G) \ E'). If W = {w} and E' = {xy}, then this notation is simplified to G - w and G - xy. Similarly, if x and y are non-adjacent vertices of G, then G xy is obtained from G by joining x to y.