Mathematics for Computer Science

Chapter 11 Simple Graphs300

simple 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/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, namely the one whose
endpoints areuandv.

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 an 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,
does not need to have any edges at all, namelyjE.G/jcould be zero, which implies