## Introduction to Graph Theory

Graph theory is the study of mathematical objects known as “graphs” – a word to which graph theorists have given a rather special meaning. So we must start by defining exactly what a graph is.

Definition . $A$ graph $G$ is a finite nonempty set, $V(G)$, of objects, called vertices, together with a set, $E(G)$, of unordered pairs of distinct vertices. The elements of $E(G)$ are called edges.
For example, we might have
$$V(G)={1,2,3,4,5}$$
and
$$E(G)={{1,2},{1,3},{1,4},{2,3},{2,5},{3,4},{3,5},{4,5}}$$
For the sorts of results with which we are concerned, it is most convenient to consider the following geometric representation or diagram or drawing of a graph. On the page we draw a small circle to correspond to each vertex. For each edge we then draw a line between the corresponding pair of vertices. The only restriction on such a line is that it does not intersect the circle corresponding to any other vertex. For example, the above graph is represented in Figure $4.1(\mathrm{i})$, (ii) and (iii) in three ways.

If $e={u, v}$ then we say that $u$ and $v$ are adjacent vertices, and that edge $e$ is incident with vertices $u$ and $v .$ We can also say that the edge $e$ joins $u$ and $v$.

Vertices adjacent to a vertex $u$ are called neighbours of $u$. The set of neighbours of $u$ is denoted $N(u) .$ A graph is completely specified by the pairs of vertices that are adjacent, and the only function of a line in the drawing, representing an edge, is to indicate that two vertices are adjacent. In (i) of Figure $4.1$, no edge crosses another; in (ii) of Figure $4.1$, the edge ${1,4}$ crosses edges ${2,5}$ and ${3,5}$. A graph which can be represented with no edges crossing is said to be planar, so our graph $G$ is planar by Figure $4.1(\mathrm{i})$

We give a few examples to illustrate the variety of settings in which graphs arise.

Example The word graph $W_{n}$ is the graph having $V\left(W_{n}\right)$ equal to the set of all English words having exactly $n$ letters. Two words are adjacent if one can be obtained from the other by replacing exactly one letter by another (in the same position). For example, seat is adjacent to sent in $W_{4} .$ In Figure $4.2$ we show a drawing of part of $W_{3}$

Example Given the street map of a city, one can define a street map graph as follows. There is a vertex for each street intersection, and an edge for each part of a street joining two intersections and traversing no other intersections. An example is given in Figure 4.3, where intersections are numbered to make the correspondence clear. Such graphs are useful in solving certain kinds of routing and scheduling problems, such as garbage pickup, or delivery of newspapers to carriers.