In topology we think of a graph as a 1-dimensional geometric object, vertices being
points and edges being curves connecting these points in pairs. This view is dif-
ferent from but compatible with the interpretation of a graph common in discrete
mathematics where the vertices are abstract elements and the edges are pairs of
these elements. In more than one way, this book lives in the tension between the
discrete and the continuous, and graphs are just one example of this phenomenon.
We begin with the discussion of an intrinsic property, namely whether a graph is
connected or not. Indeed, this does not depend on where we draw the graph, on
paper or in the air. Following are extrinsic considerations about curves and graphs
in the plane and in 3-dimensional space. While the extrinsic questions are natural
to most people, the mathematician usually favors the intrinsic point of view since
it tends to lead to more fundamental insights of more general validity.
I.1 Connected Components
A theme that goes through this entire book is the exchange between discrete and
continuous models of reality. In this first section, we compare the notion of con-
nectedness in discrete graphs and continuous spaces.
Simple graphs. An abstract graph is a pair G = (V, E) consisting of a set of
vertices, V , and a set of edges, E, each a pair of vertices. We draw the vertices as
points or little circles and the edges as line segments or curves connecting the points.)(
The graph is simple if the edge set is a subset of the set of unordered pairs, E ⊆
which means that no two edges connect the same two vertices and no edge joins
vertex to itself. For n = card V vertices, the number of edges is m = card E ≤
Every simple graph with n vertices is a subgraph of the complete graph, Kn, that
contains an edge for every pair of vertices; see Figure I.1.