Chapter I

Graphs

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 ⊆

V

2

,

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 ≤

(

n

2

)a

.

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.

3

http://dx.doi.org/10.1090/mbk/069/01