Chapter 1 - Mathematical Models

Chapter 2 - Elementary Concepts of Graph Theory

1.1 Nonmathematical Models

1.2 Mathematical Models

1.3 Graphs

1.4 Graphs as Mathematical Models

1.5 Directed Graphs as Mathematical Models

1.6 Networks as Mathematical Models

2.1 The Degree of a Vertex

2.2 Isomorphic Graphs

2.3 Connected Graphs

2.4 Cut-Vertices and Bridges

Probably the best way to learn what “mathematical models” are is to look at examples. This is what we shall do in this chapter. We begin, however, by retreating one step to the word “model,” since models need not be mathematical. We shall see that the difficulties involved in “constructing” mathematical models may be very similar to the steps in building nonmathematical models.

What exactly does the word “model” mean? Let us consider some uses of this word. Suppose you, the reader, and your husband (perhaps you have a different “model” of a reader!) have received in the mail a brochure which advertises a new land development near your city, including private houses, apartment complexes, and shopping areas. The brochure shows a map of this area. Curved and straight lines represent roads, rectangles represent houses, and other diagrams represent other aspects of this new development. You know, of course, that the map and what it displays is not the actual land development. It is only a model of the development.

You have been considering moving from your current apartment, so, with the aid of the map, you and your husband drive to the apartment complex. This drive turns out to be more difficult than anticipated since all the roads leading into the area are dirt roads and very bumpy. (The map didn’t mention that!) You arrive at the office of the apartment complex, and in the middle of the room is a large table displaying a miniature model of the entire complex. This allows you to see the location of the apartment buildings as well as the office, the swimming pool, the roads, and the children’s play area. Several things which are important to you (such as the location of laundry facilities and carports) are not shown in the model, so you ask about these.

You are interested in this new apartment complex and you would like to see what a typical 2-bedroom apartment looks like. So you are directed to a model apartment. Although all the apartments available are unfurnished, the model apartment is furnished to help you determine its appearance once you have moved in. However, the model apartment is a bit misleading, for it has been elegantly decorated by a local furniture store while your furniture is perhaps quite ordinary at best.

We have now seen three examples of models. In each case, the model is a representation of something else. Whether the model gives an accurate enough picture of the real entity depends entirely on which features are important to you.

How else is the word “model” used? Perhaps you (a different reader) think of an attractive young woman modeling a swimsuit. In this case, the manufacturer or a department store is trying to sell swimsuits, and rather than displaying them at a counter, they are having a model give you an idea of how the suit would look on your wife (or your sister) if you were to buy it. In this case, the model may not give you a very accurate picture of what the swimsuit will look like on the person for whom it is purchased; on the other hand, you may not care.

Another common use of the word “model” is in “model car” or “model airplane.” Perhaps you’d like to build a model of a 1956 Thunderbird. There are model kits available for this purpose, but these may not be satisfactory if you would like your model to illustrate the dashboard. There must be some limitations on the detail of your model, or otherwise, the only possibility is to purchase your own 1956 Thunderbird.

Intuitively, then, a model is something which represents something else. It may be smaller, larger, or approximately the same size as the thing it represents. It illustrates certain key features (but not all features) of the real thing. What features it possesses depends completely on the construction of the model. Ideally, a model should possess certain predetermined characteristics. Whether such a model can be built is often the crucial problem.

In a mathematical model, we represent or identify a real-life situation or problem with a mathematical system. One of the best-known examples of this representation is plane Euclidean geometry or plane trigonometry, which gives useful results for describing small regions, such as measuring distances. For example, the map of a state would be very useful for determining distances between towns and cities in the state, but in many instances a map of the world would not be as helpful as a globe, say, for calculating distances between certain cities. To indicate how varied mathematical models may be, we present several examples.

Example 1.1

For investment purposes, you have been building apartment houses the past three years. In particular, three years ago you built a 4-apartment building for $100,000. Two years ago, you raised a 6-apartment building for $140,000, and last year you completed an 8-apartment building for $180,000. You are now considering your construction plans for the current year. What kind of mathematical model would represent this situation? You might observe that in each case the cost C of the apartment building equals the sum of $20,000 and the product of the number n of apartments and $20,000, that is,

\(C=20,000+20,000n\)

for n = 4, 6, 8. We might use this formula, then, to model the cost of apartment buildings.

Example 1.2

You left a jug of wine sitting in your car and its temperature is 70°F when you remove it. You place the jug in your refrigerator, where the temperature is 35°. After 30 minutes you observe that the temperature of the wine has dropped to 60°. What mathematical model would represent this situation? Here we might refer to a law of physics which, in this case, states that the rate of change of the temperature T of the wine is proportional to the difference between the temperatures of the wine and of the refrigerator:

\[\frac{dT}{dt}=k\left(T−35\right)\]

where k is the constant of proportionality and t denotes time. In order to arrive at an expression for T, it would be necessary to solve this differential equation.

Example 1.3

You are a member of an organization which has just purchased a new major league baseball franchise: the New Orleans Shrimps. Each of the existing major league teams has agreed to leave unprotected four of their players, and you have the option of purchasing the contract of any of these unprotected players at $75,000 each, provided no more than two players are taken from any one team. You have the records of each of these players. Naturally, you would like to obtain the best players available for your team.What mathematical model would represent this situation? First, you decide to rank pitchers according to their earned-run averages. Then, for non-pitchers, a more complicated formula is adopted. For each player’s preceding season, let h be the number of hits, H the number of home runs, r the number of runs scored, R the number of runs batted in, w the number of times the player had the winning hit, f his fielding average, and b his batting average. Then the player’s proficiency P is given by

\(P=h+5H+r+2R+10w+1000f+1000b\)

The non-pitchers are then ranked according to their player proficiencies.

Example 1.4

Suppose you are a woman beginning your senior year of college. You realize that you will graduate at the end of the school year, and you have been thinking about your future and what you will do after graduation. You have been considering several possibilities. Although you’ve heard that the job prospects for new graduates are not excellent, your grades in college have been high, and with an economics major and mathematics minor, you feel that your chances are good for getting a junior executive position with some reputable business firm. This interests you. However, you’ve been going to college for over three years, and the thought of spending several months traveling after graduation intrigues you. Many of your friends have been talking about this. You have also been thinking about pursuing a graduate degree.

This situation can be represented by the diagram of Figure 1.1, where the “states” S_{0}, S_{1}, S_{2}, and S_{3} are as follows:

- S
_{0}: You are an undergraduate (initial state). - S
_{1}: You look for a job in the business world. - S
_{2}: You travel with your friends. - S
_{3}: You go to graduate school.

You now know what the alternatives are, but what decision should you make? Such a decision requires more information. After thinking this over, you decide the following criteria are most important to you:

- How interesting this activity will be.
- How this will eventually affect your getting an interesting and challenging job.
- How this affects your meeting young men.
- How this will affect your immediate financial status.
- How much free time this will give you.

You decide to assign 1, 2, or 3 points to each of these factors in each alternative state. The values assigned are:

S_{1} | S_{2} | S_{3} | |

interesting activity | 2 | 3 | 2 |

eventual job | 2 | 1 | 3 |

meeting young men | 2 | 2 | 3 |

financial status | 3 | 1 | 1 |

free time | 1 | 3 | 2 |

— | — | — | |

10 | 10 | 11 |

Therefore you decide to go to graduate school. Now where do you apply?—that’s another decision.

Example 1.5

You own a rather exclusive golf course in the country, and you are trying to decide what you should charge for a round of golf. You decide to try an experiment. You charge $11.75 one day and 50 golfers play that day. When you charge $11.00, a total of 100 people pay to play golf. When you charge $9.75, the number of golfers totals 150. What mathematical model would represent this situation? First we observe that for x = 50, 100, 150, the price p which is being charged is given by

\(p=12−0.0001x^2\)

Hence, we might choose this formula as our model.

Before proceeding further with illustrations of mathematical models, we pause to introduce the concept of a “graph.” As the title of this book indicates, we shall encounter this concept many times. A graph G is a finite nonempty set V together with an irreflexive, symmetric relation R on V. Since R is symmetric, for each ordered pair (u, v) ∈ R, the pair (v, u) also belongs to R. We denote by E the set of symmetric pairs in R. For example, a graph G may be defined by the set

V = {v_{1}, v_{2}, v_{3}, v_{4}}

together with the relation

R = {(v_{1},v_{2}), (v_{1}, v_{3}), (v_{2},v_{1}), (v_{2},v_{3}), (v_{3},v_{1}), (v_{3},v_{2}), (v_{3},v_{4}), (v_{4},v_{3})}.

In this case,

E = {{(v_{1},v_{2}), (v_{2},v_{1})}, {(v_{1},v_{3}), (v_{3},v_{1})}, {(v_{2},v_{3}), (v_{3},v_{2})}, {(v_{3},v_{4}), (v_{4},v_{3})}}.

In a graph G, we refer to V as the vertex set, each element of V being called a vertex (the plural is “vertices ”). The number of vertices in G is called the order of G. Each element of E (that is, each set consisting of two symmetric ordered pairs from R) is called an edge, and E itself is called the edge set of G. The number of edges in G is called the size of G. Hence, |V| = order of G and |E| = size of G.

If G is a graph defined in terms of a vertex set V and a relation R on V, then (u, v) ∈ R implies (v, u) ∈ R. Hence, {(u, v), (v, u)} is an edge of G. It is convenient to denote such an edge by uv (or, equivalently, vu). The edge set E completely determines the relation R; indeed, it is customary to describe a graph in terms of its vertex set and edge set. The graph G illustrated above could then be defined in terms of the sets V = {v_{1}, v_{2}, v_{3}, v_{4}} and E = {v_{1}v_{2}, v_{1}v_{3}, v_{2}v_{3}, v_{3}v_{4}}. Therefore, the order of G is four, as is its size.

Occasionally it is desirable to denote the vertex set and edge set of a graph G by V(G) and E(G), respectively. This is particularly useful when there are two or more graphs under consideration.

Since the empty subset of V × V is an irreflexive and symmetric relation on V, it follows that the edge set of a graph may be empty, i.e., a graph may have no edges. Of course, by definition, every graph has vertices.

In dealing with graphs, it is often convenient to represent them by means of diagrams. In such a representation, we indicate the vertices by points or small circles, and we represent the edges by line segments or curves joining the two appropriate points. The line segments or curves are drawn so that they pass through no point other than the two points they join. Diagrams of the graph G previously described are given in Figure 1.2. The first diagram uses only straight line segments, while the second diagram employs curved lines. Although the two diagrams look quite different, they contain exactly the same vertices and the same edges, and so they describe the same graph. Notice that in the second diagram, the line segments representing the edges v_{1}v2 and v3v4 intersect. This is quite permissible (in fact, it may be unavoidable), but you should not confuse this point of intersection with a vertex. As mentioned earlier, for this example, there are four vertices.

Since a diagram of a graph (such as the diagram shown in Figure 1.2) completely describes the graph, it is customary and convenient to refer to the diagram of a graph G as G itself. A few elementary definitions are now in order. (Many of these are inspired by the geometric aspect of graphs.)

If e = uv ∈ E(G) (i.e., if uv is an edge of a graph G), then we say e joins the vertices u and v. Two vertices u and v are adjacent in a graph G if uv ∈ E(G). We say that u and v are adjacent to or adjacent with each other. If uv ∉ E(G), then u and v are nonadjacent vertices. If e = uv ∈ E(G), then u and v are each incident to or incident with e. If uv and uw are distinct edges of a graph G (i.e., v ≠ w), then uv and uw are adjacent edges. Hence, in the graph G of Figure 1.2, v_{1} and v_{3} are adjacent, but v_{1}, and v_{4} are not adjacent. The vertex v_{3} is incident to the edge v_{2}v_{3}, but v_{4} is not incident to v_{2}v_{3}. The edges v_{1}v_{3} and v_{3}v_{4} are adjacent, but v_{1}v_{2} and v_{3}v_{4} are not adjacent.

The construction of mathematical models may take many forms and may involve many areas of mathematics. One area of mathematics particularly well-suited to model building is graph theory. In this section we present examples of situations and describe the appropriate graphs that serve as mathematical models. At this point, we make no attempt to consider detailed problems. We shall delay discussion of problems until Chapter 3.

Example 1.6

A grade-school teacher wishes to make a seating chart for her class. How she constructs the seating chart may depend on which students are friends of each other. The class can be “pictured” by means of a graph, where the vertices represent the students and friendship between two students is indicated by an edge between the appropriate vertices.

Example 1.7

Several army platoons are deployed in various locations in preparation for a battle. Communication is handled by battery-powered telephone. Two platoons can communicate directly with each other if they are sufficiently close. A model of this situation would be a graph where the vertices represent the platoons and direct communication between two platoons is represented by an edge between the two appropriate vertices.

Example 1.8

A number of islands are located in the Pacific Ocean off the California coast. Suppose a line of ferryboats operates from the mainland to certain of the islands. Suppose further that boats travel between several islands as well. This situation can be represented by means of a graph, where the vertices denote the islands and the mainland (one vertex for each island and one for the mainland). Two vertices are joined by an edge if you can travel by boat directly between the land areas.

A directed graph D (often called a digraph) is a finite nonempty set V together with an irreflexive relation R on V. As with graphs, the elements of V are called vertices. Each ordered pair in R is referred to as a directed edge or arc (the word “edge” is not used in digraphs). For consistency with the notation introduced for graphs, we shall denote the relation by E rather than by R when dealing with digraphs.

Since the defining relation of a digraph D need not be symmetric, it follows that if (u, v) is an arc of D, then (v, u) need not be an arc of D. This situation would be indicated in a diagram of D by drawing a line segment or curve between the points representing u and v and inserting an arrowhead that “directs” the line segment from u to v. Should both (u, v) and (v, u) be arcs of D, then, ordinarily, we would draw two curves (which do not cross) between u and v, and place an arrowhead on each curve in opposite directions.

If we let V_{1}= {v_{1}, v_{2}, v_{3}, v_{4}} and E_{1}= {(v_{1}, v_{2}), (v_{2}, v_{3}), (v_{3}, v_{2})}, then we have described a digraph, say D_{1}. The digraph D_{1} can be indicated pictorially, as in Figure 1.3. Again we shall follow the custom of referring to a diagram of a digraph as the digraph itself.

It may happen that the relation defining a digraph D is symmetric. We refer to such digraphs as symmetric digraphs. Of course, symmetric digraphs are then graphs. The only real difference between a symmetric digraph and a graph is how they are represented pictorially. For example, Figure 1.4 shows a symmetric digraph D and its graphical counterpart G.

There are certain situations for which digraphs yield a more acceptable mathematical model than graphs can provide. We consider two examples.

Example 1.9

A large New York business firm has a rather complex structure. We can represent this structure by a digraph D. Namely, we identify a vertex of D with each individual working in the firm. Then we draw an arc from vertex u to vertex v if the individual associated with v is a subordinate of the individual associated with u.

Example 1.10

A city has several one-way streets as well as two-way streets. The traffic pattern of the city may be indicated by means of a digraph. For example, we could represent the street intersections by vertices, and introduce an arc from u to v if it is possible to drive legally from the intersection associated with u to the intersection associated with v without passing through any other intersection.

Just as there are instances when digraphs are more suitable than graphs as mathematical models for certain situations, there are occasions when neither graphs nor digraphs are entirely appropriate as mathematical models, although graphs or digraphs appear to be involved. In this section we consider some other alternatives.

By a network we mean a graph or digraph together with a function which maps the edge set into the set of real numbers. (The word “network” is used because of its connection with electrical networks.) A network resulting from a graph is called an undirected network, while a network resulting from a digraph is called a directed network. Examples of each are shown in Figure 1.5.

A signed graph S is an undirected network whose functional values are + 1 or −1. Since a positive or negative sign is attached to every edge of S, it is natural to refer to each edge of a signed graph as a positive edge or negative edge. For example, if

V = {v_{1}, v_{2}, v_{3}},

E = {v_{1}v_{2}, v_{1}v_{3}, v_{2}v_{3}},

and

f = {(v_{1}v_{2}, + 1), (v_{1}v_{3}, −1), (v_{2}v_{3}, −1)},

then the resulting signed graph can be represented in one of two ways, as shown in Figure 1.6.

Example 1.11

A neighborhood consists of several families. Two families may be friendly toward each other, unfriendly, or may be indifferent toward (or may not even be acquainted with) each other. This situation can be represented by a signed graph S, where the vertices are joined by a positive edge if the corresponding families are friendly, by a negative edge if the corresponding families are unfriendly, and by no edge otherwise.

Undirected networks whose functional values are positive integers often serve as mathematical models. There are two common ways to represent such undirected networks. For example, if

V = {v_{1}, v_{2}, v_{3}},

E = {v_{1}v_{2}, v_{1}v_{3}, v_{2}v_{3}},

and

f = {(v_{1}v_{2}, 2), (v_{1}v_{3}, 1), (v_{2}v_{3}, 3)},

then the resulting undirected network can be represented as shown in Figure 1.7(a) or Figure 1.7(b).

If such an undirected network is represented as a set of points in the plane and the points are joined by an integral number of curves or line segments [as in Figure 1.7(b)], then the network is called a multigraph. Let M be a multigraph with edge set E and associated function f. If uv ∈ E and f(uv) = n, where n is a positive integer, then we say u and v are joined by n edges, and we refer to these edges as multiple edges.

Example 1.12

Let v_{1}, v_{2}, and v_{3} be three villages, and suppose a road runs between every two villages. The quality of the roads and the distances between villages make the walking times between the villages as follows:

- between v
_{1}and v_{2}, two days; - between v
_{1}and v_{3}, one day; - between v
_{2}and v_{3}, three days.

This situation can be represented as in Figure 1.7(a).

Example 1.13

Suppose v_{1}, v_{2}, and v_{3} are three villages, and suppose there are two roads between v_{1} and v_{2}, one road between v_{1} and v_{3}, and three roads between v_{2} and v_{3}. This situation can be represented as in Figure 1.7(b).

In all the relations we have considered in this chapter, we have assumed irreflexivity. It is quite possible that in the situation under discussion, the relation is not irreflexive. In this’case, we refer to the ordered pair (u, u) as a loop. If we remove the restriction “irreflexive” in the definition of graph, we call the result a loop-graph. Loopdigraphs, loop-networks, and loop-multigraphs are defined analogously. Loop-multigraphs are also called pseudographs.

Let

V = {v_{1}, v_{2}, v_{3}, v_{4}}

and

E = {(v_{1}, v_{2}), (v_{2}, v_{3}), (v_{3}, v_{2}), (v_{3}, v_{3}), (v_{4}, v_{4})}.

This is a loop-digraph, which could be drawn as indicated in Figure 1.8.

We have already introduced two numbers associated with a graph G, namely the order and the size. Now we define a collection of numbers associated with G. Let v be a vertex of G. The number of edges of G incident with v is called the degree of v in G. The degree of v is denoted by deg_{G} v, or simply deg v if the graph is clear by context. For the graph G of Figure 2.1, deg v_{1} = 1, deg v_{2} = 2, deg v_{3} = 3, deg v_{4} = 2, and deg v_{5} = 0.

By a (p, q) graph we mean a graph having order p and size q. The graph G of Figure 2.1 is a (5, 4) graph. We might observe that for this graph, the sum of the degrees of its vertices is 8, which, in this case, equals 2q. This is no mere coincidence, as we now show.

Theorem 2.1

For any graph G, the sum of the degrees of the vertices of G equals twice the number of edges of G. Symbolically, if G is a (p, q) graph with vertices v_{1}, v_{2}, . . . , v_{p}, then

Σi=1p deg v_{i} = 2q

Proof

When summing the degrees of the vertices of a graph G, we count each edge of G twice, once for each of the two vertices incident with the edge. ▋

A vertex is called even or odd according to whether its degree is even or odd. The graph G of Figure 2.1 has two odd vertices and three even vertices. The following result is a consequence (or corollary) of Theorem 2.1.

Theorem 2.2

Every graph contains an even number of odd vertices.

Proof

Let G be a graph. If G contains no odd vertices, then the result follows immediately. Suppose that G contains k odd vertices; denote them by v_{1}, v_{2}, . . . , v_{k}. If G contains even vertices as well, then denote these by u_{1}, u_{2}, . . . , u_{n}. By Theorem 2.1,

(deg v_{1} + deg v_{2} + . . . + deg v_{k}) + (deg u_{1} + deg u_{2} + . . . + deg u_{n}) = 2q,

where q is the number of edges in G. Since each of the numbers deg u_{1}, deg u_{2}, . . . , deg u_{n} is even, (deg u_{1} + deg u_{2} + . . . + deg u_{n}) is even, so we have

(deg v_{1} + deg v_{2} + . . . + deg v_{k}) = 2q - (deg u_{1} + deg u_{2} + . . . + deg u_{n}) is even.

However, each of the numbers deg v_{1}, deg v_{2}, . . . , deg v_{k} is odd. Therefore, k must be even; that is, G has an even number of odd vertices. If G has no even vertices, then we have (deg v_{1} + deg v_{2} + . . . + deg u_{k}) = 2q, from which we again conclude that k is even. ▋

If every vertex of a graph G has the same degree r, we say that G is regular of degree r or is r-regular. A graph is complete if every two of its vertices are adjacent. A complete graph of order p is (p − 1)-regular and is denoted by K_{p}. Five complete graphs are shown in Figure 2.2.

In every area of mathematics, it is important to know whether two objects under investigation are the same (in some sense) or are different. For example, the numbers 2 and 6/3 are considered to be the same, or equal, but they are certainly not identical. We now wish to determine what conditions must hold for two graphs to be “equal.” The importance of knowing this equality lies in the fact that if G_{1} and G_{2} are two equal graphs which are models of two situations, then there is something basically similar about the two situations.

Intuitively, two graphs G_{1} and G_{2} are the same if it is possible to redraw one of them, say G_{2}, so it appears identical to G_{1}. For example, the graphs G_{1} and G_{2} of Figure 2.4 have this property.

We refer to two equal graphs as “isomorphic graphs.” We now give a more formal definition of this concept. Let G_{1} and G_{2} be two graphs. By an isomorphism from G_{1} to G_{2} we mean a one-to-one mapping φ : V(G_{1}) → V(G_{2}) from V(G_{1}) onto V(G_{2}) such that two vertices u_{1} and v_{1} are adjacent in G_{1} if and only if the vertices φ(u_{1}) and φ(v_{1}) are adjacent in G_{2}. We then say that G_{1} and G_{2} are isomorphic if an isomorphism exists from G_{1} to G_{2}. If φ is an isomorphism from G_{1} to G_{2}, then the inverse mapping φ^{−1} (see Exercise A.25) from V(G_{2}) to V(G_{1}) also satisfies the definition of isomorphism. If G_{1} and G_{2} are isomorphic graphs, we can say that G_{1} is isomorphic to G_{2} and that G_{2} is isomorphic to G_{1}.

An important property of isomorphism is contained in the following theorem.

Theorem 2.3

The relation “is isomorphic to” is an equivalence relation on the set of all graphs.

Proof

The fact that the relation “is isomorphic to” is reflexive follows immediately. We need only observe that if G is a graph and the mapping φ : V(G) → V(G) is defined by φ(v) = v for all v ∈ V(G), then φ is an isomorphism from G to G, i.e., G is isomorphic to G.

Suppose G_{1} is isomorphic to G_{2}; that is, suppose φ is an isomorphism from G_{1} to G_{2}. Define the inverse−mapping φ^{−1}: V(G_{2}) → V(G_{1}) by φ^{−1}(v_{2}) = v_{1} if φ(v_{1}) = v_{2}. By Exercise A.25, φ^{−1} is a one-to-one mapping from V(G_{2}) onto V(G_{1}). Suppose u_{2}, v_{2} ∈ V(G_{2}), and φ^{−1} (u_{2}) = u_{1} and φ^{−1}(v_{2}) = v_{1}. Then φ(u_{1}) = u_{2} and φ(v_{1}) = v_{2}. From these last equalities, u_{2} and v_{2} are adjacent if and only if φ(u_{1}) and φ(v_{1}) are adjacent, and since G_{1} is isomorphic to G_{2}, φ(u_{1}) and φ(v_{1}) are adjacent if and only if u_{1} = φ^{−1}(u_{2}) and v_{1} = φ^{−1}(v_{2}) are adjacent. Therefore, u_{2} and v_{2} are adjacent if and only if φ^{−1}(u_{2}) and φ^{−1}(v_{2}) are adjacent. This shows that G_{2} is isomorphic to G_{1}, i.e. “is isomorphic to” is a symmetric relation.

We still must show that the relation is transitive. Suppose that G_{1} is isomorphic to G_{2} and that G_{2} is isomorphic to G_{3}. Hence there exist isomorphisms α: V(G_{1}) → V(G_{2}) and β: V(G_{2}) → V(G_{3}). Consider the composite mapping β ⃘ α. By Theorems A.4 and A.5 (page 254), β ⃘ α is a one-to-one mapping from V(G_{1}) onto V(G_{3}). Let u_{1}, v_{1} ∈ V(G_{1}). Suppose that α(u_{1}) = u_{2} and α(v_{1}) = v_{2}, and that β(u_{2}) = u_{3} and β(v_{2}) = v_{3}. Since α and β are isomorphisms, u_{1} and v_{1} are adjacent if and only if α(u_{1}) = u_{2} and α(v_{1}) = v_{2} are adjacent; and u_{2} and v_{2} are adjacent if and only if β(u_{2}) = u_{3} and β(v_{2}) = v_{3} are adjacent. Thus, u_{1} and v_{1} are adjacent if and only if u_{3} = (β ⃘ α)(u_{1}) and v_{3} = (β ⃘ α)(v_{1}) are adjacent. This completes the proof that β ⃘ α is an isomorphism.

Hence, G_{1} is isomorphic to G_{3}. ▋

By Theorem A.2, it follows that the equivalence relation “is isomorphic to” partitions the set of all graphs into equivalence classes. Hence, two graphs which belong to the same equivalence class are isomorphic, while two graphs belonging to different equivalence classes are not isomorphic (that is, they are considered different graphs).

If G_{1} and G_{2} are isomorphic graphs, then, by definition, there exists a one-to-one mapping φ from V(G_{1}) onto V(G_{2}). This implies that V(G_{1}) and V(G_{2}) have the same number of elements; that is, G_{1} and G_{2} have the same order. Let u_{1} and v_{1} be two vertices of G_{1}, and suppose that φ(u_{1}) = u_{2} and φ(v_{1}) = v_{2}. Then u_{1} and v_{1} are adjacent in G_{1} if and only if u_{2} and v_{2} are adjacent in G_{2}, or in other words, u_{1}v_{1} is an edge of G_{1} if and only if u_{2}v_{2} is an edge of G_{2}. This implies that G_{1} and G_{2} have the same size. However, if two graphs have the same order and the same size, it does not necessarily follow that the graphs are isomorphic. For example, the two graphs of Figure 2.5 have order six and size nine, but they are not isomorphic.

It may seem a difficult problem to show that the graphs G_{1} and G_{2} of Figure 2.5 are not isomorphic, for evidently, we must verify that every one-to-one mapping from V(G_{1}) onto V(G_{2}) [or from V(G_{2}) to V(G_{1})] fails to be an isomorphism. However, we can simplify the problem immensely by making some pertinent observations. In the case of the graphs G_{1} and G_{2} of Figure 2.5, consider any one-to-one mapping φ from V(G_{1}) onto V(G_{2}). The vertices v_{1}, v_{2}, and v_{5} of G_{2} are pairwise adjacent, and φ must map three vertices of G_{1} into v_{1}, v_{2}, and v_{5}. If φ is an isomorphism, then two vertices of G_{1} are adjacent if and only if the two image vertices of G_{2} under φ are adjacent. This implies that the three vertices of G_{1} whose images are v_{1}, v_{2}, and v_{5} also must be pairwise adjacent; however, G_{1} does not contain three pairwise adjacent vertices. Hence there is no isomorphism from V(G_{1}) to V(G_{2}) and G_{1} is not isomorphic to G_{2}.

A very useful necessary condition for a graph G_{1} to be isomorphic to a graph G_{2} is presented next.

Theorem 2.4

If G_{1} and G_{2} are isomorphic graphs, then the degrees of the vertices of G_{1} are exactly the degrees of the vertices of G_{2}.

Proof

Since G_{1} and G_{2} are isomorphic, there exists an isomorphism φ: V(G_{1}) → V(G_{2}). Let u be an arbitrary vertex of G_{1}, and suppose deg u = n. Suppose further that the image of u in G_{2} is v, i.e., φ(u) = v. We prove that deg v = n.

Since deg u = n, the graph G_{1} contains vertices u_{1}, u_{2}, . . . , u_{n} which are adjacent to u, while every other vertex of G_{1} is not adjacent to u. Let φ(u_{i}) = v_{i} for i = 1, 2 , . . . , n. Then v is adjacent to each of the vertices v_{1}, v_{2}, . . . , v_{n}, since φ is an isomorphism. Furthermore, these are the only vertices adjacent to v, since u is adjacent to x in G_{1} if and only if v is adjacent to φ(x) in G_{2}. Thus, deg v = n.

Because a vertex of G_{1} and its image vertex of G_{2} have the same degree, this establishes the theorem. ▋

We again emphasize that Theorem 2.4 gives a necessary condition for two graphs to be isomorphic—not a sufficient condition. That is, the vertices of two graphs may have exactly the same degrees, but may not be isomorphic. (For example, G_{1} and G_{2} of Figure 2.5 are not isomorphic.) On the other hand, if the degrees of the vertices of a graph G_{1} and the degrees of the vertices of a graph G_{2} are not the same, then by Theorem 2.4, G_{1} and G_{2} are not isomorphic.

It follows that there is only one graph of order one (necessarily having size zero); that is, if G_{1} and G_{2} are both graphs of order one, then they are isomorphic. Similarly, there is only one graph of order two and size zero, and only one graph of order two and size one. However, there are three graphs of order four and size three, shown in Figure 2.6. No two graphs in Figure 2.6 are isomorphic, but any other graph of order four and size three is isomorphic to one of the graphs of Figure 2.6. We can state this in another way: Among the graphs of order four and size three, there are three isomorphism classes. Thus, if we have four or more graphs of order four and size three, two or more of these graphs must belong to the same class.

The preceding discussion illustrates the following celebrated result from the field of combinatorics. (Note: For a real number x, the number {x} denotes the smallest integer greater than or equal to x.)

The Pigeonhole Principle

Let S be a finite set consisting of n elements, and let S_{1}, S_{2}, . . . , S_{k} be a partition of S into k subsets. Then at least one subset S_{i}, 1 ≤ i ≤ k, contains at least {n/k} elements.

Hence, if there are three equivalence classes of (4, 3) graphs (that is, k = 3), and we have four (4, 3) graphs (that is, n = 4), then there must be at least {4/3} = 2 graphs in the same equivalence class.

Probably the most important class of graphs is the class of connected graphs. In this section we discuss connected graphs together with some related concepts.

Let G be a graph. A graph H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G). If a graph F is isomorphic to a subgraph H of G, then F is also called a subgraph of G. Figure 2.11 shows a graph G and a subgraph H.

Let u and v be vertices of a graph G. A u−v walk in G is an alternating sequence of vertices and edges of G, beginning with u and ending with v, such that every edge joins the vertices immediately preceding it and following it. For example, v_{3}, v_{3}v_{2}, v_{2}, v_{2}v_{6}, v_{6}. v_{6}v_{3}, v_{3}, v_{3}v_{4}, v_{4}, v_{4}v_{5}, v_{5}, v_{5}v_{4}, v_{4} is a v_{3}−v_{4} walk in the graph G of Figure 2.11. Observe that the edge v_{4}v_{5} appears twice in this walk. We need only list the vertices in a walk, for the edges are then obvious. The walk just described can therefore be expressed more simply as v_{3}, v_{2}, v_{6}, v_{3}, v_{4}, v_{5}, v_{4}.

A u−v trail in a graph is a u−v walk which does not repeat any edge. The v_{3}−v_{4} walk described above is not a v_{3}−v_{4} trail; however, v_{3}, v_{2}, v_{6}, v_{3}, v_{4} is a v_{3}−v_{4} trail in the graph G of Figure 2.11. A u−v path is a u−v walk (or u−v trail) which does not repeat any vertex. Again, in the graph G of Figure 2.11, v_{3}, v_{5}, v_{4} is a v_{3}−v_{4} path.

Two vertices u and v in a graph G are connected if u = v, or if u ≠ v and a u−v path exists in G. A graph G is connected if every two vertices of G are connected; otherwise, G is disconnected.

A connected subgraph H of a graph G is called a component of G if H is not contained in any connected subgraph of G having more vertices or edges than H. For example, the graph of Figure 2.12 has four components. If a graph has only one component, the graph is connected.

A u−v trail in which u = v and which contains at least three edges is called a circuit. In other words, a circuit must end at the same vertex with which it began. A circuit which does not repeat any vertices (except the first and last) is called a cycle. For example, in the graph G of Figure 2.13, v_{1} v_{2}, v_{3}, v_{5}, v_{2}, v_{6}, v_{1} is a circuit but is not a cycle, while v_{2}, v_{4}, v_{3}, v_{5}, v_{2} is a cycle (as well as a circuit).

By definition, a trail is an alternating sequence of vertices and edges, although we have agreed to represent a trail by a sequence of vertices. The sets of vertices and of edges determined by a trail produce a subgraph; it is also customary to refer to this subgraph as a trail. For example, v_{1}, v_{2}, v_{5}, v_{3}, v_{2}, v_{6} is a trail in the graph G of Figure 2.13. If we define the subgraph H of G by V(H) = {v_{1}, v2, v_{5}, v_{3}, v_{6}} and E(H) = {v_{1}v_{2}, v_{2}v_{5}, v_{5}v_{3}, v_{3}v_{2}, v_{2}v_{6}}, then H is also called a trail in G. More generally, it is customary to consider the subgraph consisting of the vertices and edges of a trail, path, circuit, or cycle as the respective trail, path, circuit, or cycle.

We now introduce a class of vertices and a class of edges which are important and similar in many ways.

If e is an edge of a graph G, then G − e is the subgraph of G possessing the same vertex set as G and having all edges of G except e. If v is a vertex of a graph G containing at least two vertices, then G − v is the subgraph of G whose vertex set consists of all vertices of G except v and whose edge set consists of all edges of G except those incident with v. Figure 2.15 illustrates these concepts.

A vertex v in a connected graph G is called a cut-vertex if G − v is disconnected. The vertex v_{3} of the graph G in Figure 2.15 is a cut-vertex; however, no other vertex of that graph is a cut-vertex.

Now we consider the related concept for edges. An edge e in a connected graph G is called a bridge if G − e is disconnected. The edge e_{4} of the graph G in Figure 2.15 is a bridge, but no other edge of that graph is a bridge.

If v is a cut-vertex of a connected graph G, then G − v contains two or more components. However, if e is a bridge of G, then G − e has exactly two components. The following theorem shows which edges of a graph are bridges.

Theorem 2.5

Let G be a connected graph. An edge e of G is a bridge of G if and only if e does not lie on any cycle of G.

Proof

Let e be a bridge of G. We prove the desired result by a contradiction argument. Suppose e = uv and e does lie on a cycle, say C: u, v, w, . . . , x, u (that is, w follows v on C and x precedes u). The graph G − e contains a u−v path, namely u, x, . . . , w, v, so that u is connected to v. We now show that G − e is connected.

Let u, and v_{1} be any two vertices of G − e; we show that G − e contains a u_{1}−v_{1} path. Since G is connected, there is a u_{1}−v_{1} path P in G. If the edge e does not lie on P. then P is also a path in G − e and u, is connected to v_{1} in G − e. Suppose the edge e lies on P. Then the path P can be expressed as u_{1}, . . . , u, v, . . . , v_{1}, or u_{1}, . . . , v, u, . . . , v_{1}. In the first case, u_{1} is connected to u and v is connected to v_{1} in G − e, and in the second case, u_{1} is connected to v and u is connected to v_{1}. We have already observed that u is connected to v in G − e. By Exercise 2.44, the relation “is connected to” is an equivalence relation on V(G − e); hence the relation is transitive, implying that u_{1} is connected to v_{1}. Therefore, if e belongs to a cycle, then G − e is connected and e is not a bridge. This produces the desired contradiction.

Conversely, suppose e = uv is an edge which lies on no cycle of G. Again, we give a proof by contradiction. Assume that e is not a bridge. Then G − e is connected, and thus, there is a u−v path P in G − e. However, P together with e produces a cycle in G containing e. Hence, we have a contradiction. ▋