Mathematics for Computer Science

Chapter 11 Simple Graphs394

graph only has an undirected edge,hv—wi, that connectsvandw.

Definition 11.1.1.Asimple graph,G, consists of a nonempty set,V.G/, called the
verticesofG, and a setE.G/called theedgesofG. An element ofV.G/is called
avertex. A vertex is also called anode; the words “vertex” and “node” are used
interchangeably. An element ofE.G/is anundirected edgeor simply an “edge.”
An undirected edge has two verticesu¤ vcalled itsendpoints. Such an edge
can be represented by the two element setfu;vg. The notationhu—videnotes this
edge.

Bothhu—viandhv—uidefine the same undirected edge, whose endpoints are
uandv.

b

g

h

i

f d

c e

a

Figure 11.1 An example of a graph with 9 nodes and 8 edges.

For example, letHbe the graph pictured in Figure 11.1. The vertices ofH
correspond to the nine dots in Figure 11.1, that is,

V.H/Dfa;b;c;d;e;f;g;h;ig:

The edges correspond to the eight lines, that is,

E.H/Dfha—bi;ha—ci;hb—di;hc—di;hc—ei;he—fi;he—gi;hh—iig:

Mathematically, that’s all there is to the graphH.

Definition 11.1.2. Two vertices in a simple graph are said to beadjacentiff they
are the endpoints of the same edge, and an edge is said to beincidentto each of its
endpoints. The number of edges incident to a vertexvis called thedegreeof the
vertex and is denoted by deg.v/. Equivalently, the degree of a vertex is the number
of vertices adjacent to it.

For example, for the graphHof Figure 11.1, vertexais adjacent to vertexb, and
bis adjacent tod. The edgeha—ciis incident to its endpointsaandc. Vertexh
has degree 1,dhas degree 2, and deg.e/D 3. It is possible for a vertex to have
degree 0, in which case it is not adjacent to any other vertices. A simple graph,G,