GRAPHS AND MULTIGRAPHS

GRAPHS AND MULTIGRAPHS
A graph G consists of two things:
(i) A set V = V (G) whose elements are called vertices, points, or nodes of G.
(ii) A set E = E(G) of unordered pairs of distinct vertices called edges of G.
We denote such a graph by G(V,E) when we want to emphasize the two parts of G. Vertices u and v are said to be adjacent or neighbors if there is an edge e = {u, v}. In such a case, u and v are called the endpoints of e, and e is said to connect u and v. Also, the edge e is said to be incident on each of its endpoints u and v. Graphs are pictured by diagrams in the plane in a natural way. Specifically, each vertex v in V is represented by a dot (or small circle), and each edge e = {v1, v2} is represented by a curve which connects its endpoints v1 and v2 For example, Fig. 8-5(a) represents the graph G(V,E) where:
(i) V consists of vertices A, B, C, D.
(ii) E consists of edges e1 = {A,B}, e2 = {B,C}, e3 = {C,D}, e4 = {A,C}, e5 = {B,D}.
In fact, we will usually denote a graph by drawing its diagram rather than explicitly listing its vertices and edges.
Multigraphs
Consider the diagram in Fig. 8-5(b). The edges e4 and e5 are called multiple edges since they connect the same endpoints, and the edge e6 is called a loop since its endpoints are the same vertex. Such a diagram is called a multigraph; the formal definition of a graph permits neither multiple edges nor loops. Thus a graph may be defined to be a multigraph without multiple edges or loops.
Remark: Some texts use the term graph to include multigraphs and use the term simple graph to mean a graph without multiple edges and loops.
Degree of a Vertex
The degree of a vertex v in a graph G, written deg (v), is equal to the number of edges in G which contain v, that is, which are incident on v. Since each edge is counted twice in counting the degrees of the vertices of G, we have the following simple but important result.
Theorem 8.1: The sum of the degrees of the vertices of a graph G is equal to twice the number of edges in G. Consider, for example, the graph in Fig. 8-5(a).We have deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 2.
The sum of the degrees equals 10 which, as expected, is twice the number of edges. A vertex is said to be even or odd according as its degree is an even or an odd number. Thus A and D are even vertices whereas B and
C are odd vertices.
Theorem 8.1 also holds for multigraphs where a loop is counted twice toward the degree of its endpoint. For example, in Fig. 8-5(b) we have deg(D) = 4 since the edge e6 is counted twice; hence D is an even vertex.
A vertex of degree zero is called an isolated vertex.
Finite Graphs
Amultigraph is said to be finite if it has a finite number of vertices and a finite number of edges. Observe that a graph with a finite number of vertices must automatically have a finite number of edges and so must be finite.
The finite graph with one vertex and no edges, i.e., a single point, is called the trivial graph. Unless otherwise specified, the multigraphs in this book shall be finite.