126 7. Graphs
Now we can at least experiment with smaller numbers. Let us have, say,
5 people: Alice, Bob, Carl, Diane, and Eve. When they first met, Alice
knew everybody else; Bob and Carl knew each other, and Carl also knew
Eve. So the numbers of acquaintances are: Alice 4, Bob 2, Carl 3, Diane 1,
and Eve 2. We have not only one but three people with an even number of
acquaintances.
It is still rather tedious to consider examples by listing people and listing
pairs knowing each other, and it is quite easy to make mistakes. We can,
however, find a graphic illustration that helps a lot. We represent each
person by a point in the plane (well, by a small circle, to make the picture
nicer), and we connect two of these points by a segment if the people
know each other. This simple drawing contains all the information we need
(Figure 7.1).
D CE BAFIGURE 7.1. The graph depicting acquaintance between our friendsA picture of this kind is called agraph. More exactly, a graph consists of
a set ofnodes(also known aspoints,orvertices) with some pairs of these
(not necessarily all pairs) connected byedges. It does not matter whether
these edges are straight or curvy; all that is important is which pairs of
nodes they connect. The set of nodes of a graphGis usually denoted by
V; the set of edges, byE. Thus we writeG=(V, E) to indicate that the
graphGhas node setVand edge setE.
The only thing that matters about an edge is the pair of nodes it con-
nects; hence the edges can be considered as 2-element subsets ofV. This
means that the edge connecting nodesuandvis just the set{u, v}. We’ll
further simplify notation and denote this edge byuv.
Can two edges connect the same pair of nodes (parallel edges)? Can an
edge connect a node to itself (loop)? The answer to these questions is, of
course, our decision. In some applications it is advantageous to allow such
edges; in others, they must be excluded. In this book, we generally assume
that a pair of nodes is connected by at most one edge, and no node is
connected to itself. Such graphs are often calledsimple graphs. If parallel
edges are allowed, the graph is often called amultigraphto emphasize this
fact.
If two nodes are connected by an edge, then they are calledadjacent.
Nodes adjacent to a given nodevare called itsneighbors.