239
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.
MATH 239Introduction to Combinatorics78%likedEasy26%Useful85%85 comments450 ratingsIntroduction to graph theory: colourings, matchings, connectivity, planarity. Introduction to combinatorial analysis: generating series, recurrence relations, binary strings, plane trees. [Note: Offered: F,W,S]Course ScheduleWinter 2022Fall 2021Spring 2021Winter 2021SectionClassEnrolledTimeDateLocationInstructorLEC 0016074302/31512:00 AM – 12:00 AMMTWThFSSuOnlineLEC 0026075233/30012:00 AM – 12:00 AMMTWThFSSuOnlineLEC 00361970/60LEC 00465700/60LEC 00570220/60LEC 00661950/60LEC 08165710/400TUT 1011096251/521:30 PM – 2:20 PMMTWThFSSuOnlineTUT 1021096346/528:30 AM – 9:20 AMMTWThFSSuOnlineTUT 1031096451/528:30 AM – 9:20 AMMTWThFSSuOnlineTUT 1041096555/526:30 PM – 7:20 PMMTWThFSSuOnlineTUT 1051096648/529:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1061096751/5211:30 AM – 12:20 PMMTWThFSSuOnlineTUT 1071096827/509:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1081096940/509:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1091097033/509:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1101097150/501:30 PM – 2:20 PMMTWThFSSuOnlineTUT 1111097250/501:30 PM – 2:20 PMMTWThFSSuOnlineTUT 1121097333/501:30 PM – 2:20 PMMTWThFSSuOnlineLast updated 2 hours ago from classes.uwaterloo.ca
