## Read an Excerpt

#### Graph Theory

**By Ronald Gould**

**Dover Publications, Inc.**

**Copyright © 2012 Ronald Gould**

All rights reserved.

ISBN: 978-0-486-32036-6

All rights reserved.

ISBN: 978-0-486-32036-6

CHAPTER 1

**Graphs**

**Section 1.0 Introduction**

For years, mathematicians have affected the growth and development of computer science. In the beginning they helped design computers for the express purpose of simplifying large mathematical computations. However, as the role of computers in our society changed, the needs of computer scientists began affecting the kind of mathematics being done.

Graph theory is a prime example of this change in thinking. Mathematicians study graphs because of their natural mathematical beauty, with relations to topology, algebra and matrix theory spurring their interest. Computer scientists also study graphs because of their many applications to computing, such as in data representation and network design. These applications have generated considerable interest in algorithms dealing with graphs and graph properties by both mathematicians and computer scientists.

Today, a study of graphs is not complete without at least an introduction to both theory and algorithms. This text will attempt to convince you that this is simply the nature of the subject and, in fact, the way it was meant to be treated.

**Section 1.1 Fundamental Concepts and Notation**

Graphs arise in many settings and are used to model a wide variety of situations. Perhaps the easiest way to adjust to this variety is to see several very different uses immediately. Initially, let's consider several problems and concentrate on finding models representing these problems, rather than worrying about their solutions.

Suppose that we are given a collection of intervals on the real line, say *C* = {*I*1, *I*2, ..., *Ik*}. Any two of these intervals may or may not have a nonempty intersection. Suppose that we want a way to display the intersection relationship among these intervals. What form of model will easily display these intersections?

One possible model for representing these intersections is the following: Let each interval be represented by a circle and draw a line between two circles if, and only if, the intervals that correspond to these circles intersect. For example, consider the set

C = {[-4, 2], [0, 1], (-8, 2], [2, 4], [4, 10)}.

The model for these intervals is shown in **Figure 1.1.1**.

Next, we consider the following old puzzle. Suppose there are three houses (call them *h*1, *h*2 and *h*3) and three utility companies (say gas (*g*), water (*w*) and electricity (*e*)). Our problem is to determine if it is possible to connect each of the three houses to each of the three utilities without crossing the service lines that run from the utilities to the houses. We model this puzzle by representing each house and each utility as a circle and drawing a line between two circles if there is a service line between the corresponding house and utility. We picture this situation in **Figure 1.1.2**. A solution to this problem would be a drawing in which no lines crossed. The drawing of **Figure 1.1.2** is not a solution to the problem, but merely an attempt at modeling the problem.

In our third problem, suppose you are the manager of a company that has four job openings (say *j*1, *j*2, *j*3 and *j*4) and five applicants *a*1, ..., *a*5 and that some of these applicants are qualified for more than one of your jobs. How do you go about choosing people to fill the jobs so that you will fill as many openings as possible? We picture such a situation in **Figure 1.1.3**. Again, each job and each applicant can be represented as a circle. This time, a line is drawn from a circle representing an applicant to each of the circles representing the jobs for which the applicant is qualified. A solution to this problem would be a set of four lines joining distinct jobs to distinct applicants, that is, one line joins each job to a distinct applicant. For example, the lines joining *j*1 and *a*2, *j*2 and *a*1, *j*3 and *a*4 and *j*4 and *a*5 constitute a solution to this problem. Since lines only join jobs to applicants, this is clearly the maximum number of lines possible. Can you find another solution? The real problem is how can we find solutions in general?

Despite the fact that these problems seem very different, we have used a similar type of diagram to model them. Such a diagram is called a graph. Formally, a *graph G* = (*V, E*) is a finite nonempty set *V* of elements called *vertices,* together with a set *E* of two element subsets of *V* called *edges.* In our example diagrams, each circle is a vertex and each line joining two vertices is an edge. If the context is not clear, we will denote *V* or *E* by *V* (*G*) or *E* (*G*), respectively, to show they come from the graph *G.* In **Figure 1.1.2**, the vertices are *h*1, *h*2, *h*3, *g, w, e* and the edges are

{h1, g}, {h1, e}, {h1, w}, {h2, g} {h2, e}, {h2, w}, {h3, e}, {h3, g}, {h3, w}.

For simplicity, we will usually denote edges by consecutively listing the vertices at either end. For example, the edge {*h*1, *g*} would be denoted *h*1*g* or *gh*1.

One of the beauties of graphs is that they may be thought of in many ways: formally as set systems, geometrically as the diagrams we have presented and algebraically, as we shall see later. Such diverse representations afford us an opportunity to use many tools in studying graphs and to apply graph models in many ways. To do this effectively, of course, we need to build more terminology and mathematical machinery.

Given a graph *G* = (*V, E*), the number of vertices in *V* is called the *order of G* and the number of edges in *E* is called the *size of G.* They shall be denoted as | *V* | and | *E* |, respectively. The interval graph of **Figure 1.1.1** has order 5 and size 6. If a graph *G* has order *p* and size *q,* we say *G* is a (*p, q*) graph. Two vertices that are joined by an edge are said to be *adjacent,* as are two edges that meet at a vertex. If two vertices are not joined by an edge, we say they are *nonadjacent* or *independent.* Similarly, two edges that do not share a common vertex are said to be *independent.* The set of all vertices adjacent to a vertex *v* is called the *neighborhood of v* and is denoted *N* (*v*). An edge between vertices *u* and *v* is said to have *u* (or *v*) as an *end vertex.* Further, the edge is said to be *incident* with *v* (or with *u*) and *v* is said to *dominate u* (also, *u* dominates *v*). The number of edges incident with a vertex *v* is called the *degree of v* and is denoted *deg v* or by *degG v* if we wish to emphasize that this occurs in the graph *G.* The minimum degree and maximum degree of a vertex in the graph *G* are denoted by δ(*G*) and Δ(*G*), respectively. A graph in which each vertex has degree *r* is called an *r-regular* graph (or simply regular). We now present the theorem traditionally called The First Theorem of Graph Theory.

**Theorem 1.1.1** Let *G* be a (*p, q*) graph and let *V* = {*v*1, *v*2, ..., *vp*}. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Consequently, any graph contains an even number of vertices of odd degree.

**Proof.** Since each edge has exactly two end vertices, the sum of the degrees counts each edge exactly twice. Thus, the sum is obtained. Since 2*q* is even, an even number of vertices of odd degree must then be present in the sum.

We have considered three problems thus far. The drawing of **Figure 1.1.1** is a solution to the first problem, and we have an idea of what a solution for one example of the third problem looks like. But the drawing given for the utilities problem does not provide a solution to that problem. This does not mean there is no solution, only that our drawing fails to provide one. What if we try other drawings (see **Figure 1.1.4**)? One of the interesting features of these drawings is the freedom we have to shape them. There are no restrictions on the size of the vertices or on the length or even the shape of the edges. These drawings are very much free-form. We are also free to choose an entirely different representation for our graph, for example the set representation we used in defining graphs. But this freedom also presents us with some difficulties. If a graph is presented in different ways, how can we determine if the presentations really represent the same graph?

Mathematicians use the term *isomorphism* to mean the "fundamental equality" of two objects or systems. That is, the objects really have the same mathematical structure, only nonessential features like object names might be different. For graphs, "fundamentally equal" means the graphs have essentially the same adjacencies and nonadjacencies. To formalize this concept further, we say two graphs *G*1 and *G*2 are *isomorphic* if there exists a 1-1 and onto function *f: V* (*G*1) ->*V* (*G*2) such that *xy* [member of] *E* (*G*1) if, and only if, *f* (*x*) *f* (*y*) [member of] *E* (*G*2) (that is, *f* preserves adjacency and nonadjacency). We use the function *f* to express the correspondence between vertices that are "essentially the same" in the two graphs. The function *f* is called an *isomorphism.*

**Example 1.1.1** The two drawings of the house-utilities graph are again shown in **Figure 1.1.5**. An isomorphism between *G*1 and *G*2 is determined by the function *f: V* (*G*1) ->*V*(*G*2) where:

f(a) = x, f(b) = r, f(c) = y, f(d) = s, f(e) = z, f(g) = t.

An isomorphism from *G*2 to *G*1 is given by *f*-1, the inverse of *f.*

Can you find other isomorphisms from *G*1 to *G*2?

A *subgraph of G* is any graph *H* such that *V* (*H*) [subset or equal to] *V* (*G*) and *E* (*H*) [subset or equal to] *E* (*G*); we also say *G contains H.* If *H* is a subgraph of *G* and *V* (*H*) = *V* (*G*), we say that *H* is a *spanning subgraph* of *G.* A more restricted but often very useful idea is the following: Given a subset *S* of *V* (*G*), the *subgraph induced by S,* denoted , is that graph with vertex set *S* and edge set consisting of those edges of *G* incident with two vertices of *S.*

The graphs in **Figure 1.1.6** illustrate these ideas. Since *V* (*H*) = *V* (*G*), *H* is a spanning subgraph of *G.* Also, *I* is an induced subgraph of *G* since all edges of *G* with both end vertices in *V* (*I*) are contained in *I.* However, *J* is not an induced subgraph of *G* since the edge from 1 to 5 is in *G,* but is not in *J.*

Several natural and useful variations on graphs will be helpful. The first is the idea of a *multigraph,* that is, a graph with (possibly) multiple edges between vertices. A *pseudograph* allows edges that begin and end at the same vertex (called a *loop*). If we think of the edge between two vertices as an ordered pair rather than a set, a natural direction from the first vertex of the pair to the second can be associated with the edge. Such edges will be called *arcs* (to maintain the historical terminology), and graphs in which each edge has such a direction will be called *directed graphs* or *digraphs.* For digraphs, the number of arcs directed away from a vertex *v* is called the *outdegree* of *v* (denoted *od v*) and the number of arcs directed into a vertex *v* is the *indegree* of *v* (denoted *id v*). Often, for emphasis, we denote the arc directed from *u* to *v* as *u* ->*v.* In a digraph, we define the *degree* of a vertex *v* to be *deg v = id v* + *od v.* If *u* ->*v* is an arc of the digraph, we say that *u dominates v* and that *v* is *dominated by u.* Sometimes we say *u* is *adjacent to v* or *v* is *adjacent from u.*

Clearly, we can produce even more variations such as pseudodigraphs, multidigraphs and pseudomultidigraphs. Although these will not play as significant a role in our study of graphs, at times they will be useful. In this text we will be sure the reader understands the kind of graph under consideration, and the term *graph* will always be as we defined it: finite order, without loops, multiple edges or directed edges.

**Section 1.2 Elementary Properties and Operations**

A quick inspection of a road map of the southern states shows several important cities and the interstates that connect them. We model a portion of this map in **Figure 1.2.1**.

It seems natural to think of a graph (or digraph) when trying to model a road system. Vertices represent cities, and edges (or arcs) represent the roads between the cities. In tracing the route from one location to another, we would traverse some sequence of roads, beginning at some starting point, and finally reaching our destination. For example, we could travel from Atlanta to Nashville by first leaving Atlanta and traveling along I75 to Chattanooga, then following I24 to Nashville. Such a model leads us naturally to formally define the following concepts.

Let *x* and *y* be two vertices of a graph *G* (not necessarily distinct vertices). An *x - y walk* in *G* is a finite alternating sequence of vertices and edges that begins with the vertex *x* and ends with the vertex *y* and in which each edge in the sequence joins the vertex that precedes it in the sequence to the vertex that follows it in the sequence. For example, in the graph of **Figure 1.2.1**, one *b - n* walk is

b, I59, c2, I75, a, I20, b, I59, c2, I24, n

while another is

b, I20, a, I85, c1, I85, a, I75, c2, I24, n.

The number of edges in a walk is called the *length* of the walk. Note that repetition of vertices and edges is allowed. Ordinarily, we will use a more compact notation for a walk by merely listing the vertices involved, noting that the edge between consecutive vertices (at least in a graph or digraph) is then implied. We will only use the full notation for walks in multigraphs, where there is a choice of edges and this choice is important, or for emphasis of the edges involved. An *x - y* walk is *closed* if *x = y* and *open* otherwise. Two walks are equal if the sequences of vertices and edges are identical.

Several stronger types of walks are also important. An *x - y trail* is an *x - y* walk in which no edge is repeated, and an *x - y path* is an *x - y* walk in which no vertex is repeated, except possibly the first and the last (if the path is closed). Clearly, a path is also a trail. We consider a single vertex as a trivial path (walk or trail). In the graph of **Figure 1.2.1**, we see that *a, b, a, c*2, *b,* is an *a - b* walk of length 4, while *a, b, c*2, *a, c*1 is an *a - c*1 trail of length 4, and *a, c*2, *n, m* is an *a - m* path of length 3.

*(Continues...)*

Excerpted fromGraph TheorybyRonald Gould. Copyright © 2012 Ronald Gould. Excerpted by permission of Dover Publications, Inc..

All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.

Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.