DOVER SCIENCE BOOKS

THE DEVELOPMENT OF MATHEMATICS, E. T. BELL. (0-486-27239-7)

507 MECHANICAL MOVEMENTS: MECHANISMS AND DEVICES, HENRY T. BROWN. (0-486-44360-4)

A REFRESHER COURSE IN MATHEMATICS, F. J. CAMM. (0-486-43225-4)

FLAWS AND FALLACIES IN STATISTICAL THINKING, STEPHEN K. CAMPBELL. (0-486-43598-9)

HARMONIC PROPORTION AND FORM IN NATURE, ART AND ARCHITECTURE, SAMUEL COLMAN. (0-486-42873-7)

THE CURVES OF LIFE, THEODORE A. COOK. (0-486-23701-X)

A SHORT HISTORY OF TECHNOLOGY: FROM THE EARLIEST TIMES TO A.D. 1900, T. K. DERRY AND TREVOR I. WILLIAMS. (0-486-27472-1)

MATHOGRAPHICS, ROBERT DIXON. (0-486-26639-7)

EINSTEIN’S ESSAYS IN SCIENCE, ALBERT EINSTEIN. (0-486-47011-3)

EXPERIMENTAL RESEARCHES IN ELECTRICITY, MICHAEL FARADAY. (0-486-43505-9)

THE GREAT PHYSICISTS FROM GALILEO TO EINSTEIN, GEORGE GAMOW. (0-486-25767-3)

THIRTY YEARS THAT SHOOK PHYSICS: THE STORY OF QUANTUM THEORY, GEORGE GAMOW. (0-486-24895-X)

ONE TWO THREE . . . INFINITY: FACTS AND SPECULATIONS OF SCIENCE, GEORGE GAMOW. (0-486-25664-2)

GRAVITY, GEORGE GAMOW. (0-486-42563-0)

FADS AND FALLACIES IN THE NAME OF SCIENCE, MARTIN GARDNER (0-486-20394-8)

RELATIVITY SIMPLY EXPLAINED, MARTIN GARDNER (0-486-29315-7)

THE GEOMETRY OF ART AND LIFE;, MATILA GHYKA. (0-486-23542-4)

UNDERSTANDING EINSTEIN’S THEORIES OF RELATIVITY: MAN’S NEW PERSPECTIVE ON THE COSMOS, STAN GIBILSCO. (0-486-26659-1)

FROM GALILEO TO NEWTON, A. RUPERT HALL. (0-486-24227-7)

MECHANICAL APPLIANCES, MECHANICAL MOVEMENTS AND NOVELTIES OF CONSTRUCTION, GARDNER D. HISCOX. (0-486-46886-0)

1800 MECHANICAL MOVEMENTS, DEVICES AND APPLIANCES, GARDNER D. HISCOX. (0-486-45743-5)

MAKERS OF MATHEMATICS, STUART HOLLINGDALE. (0-486-45007-4)

THE DIVINE PROPORTION, H. E. HUNTLEY. (0-486-22254-3)

ENGINEERING AND TECHNOLOGY, 1650-1750: ILLUSTRATIONS AND TEXTS FROM ORIGINAL SOURCES, MARTIN JENSEN. (0-486-42232-1)

SHORT-CUT MATH, GERARD W. KELLY. (0-486-24611-6)

MATHEMATICS FOR THE NONMATHEMATICIAN, MORRIS KLINE. (0-486-24823-2)

THE FOURTH DIMENSION SIMPLY EXPLAINED, HENRY P. MANNING. (0-486-43889-9)

VIOLENT PHENOMENA IN THE UNIVERSE, JAYANT V. NARLIKAR (0-486-45797-4)

BASIC MACHINES AND HOW THEY WORK, NAVAL EDUCATION. (0-486-21709-4)

EXCURSIONS IN GEOMETRY, C. STANLEY OGILVY. (0-486-26530-7)

MUSIC, PHYSICS AND ENGINEERING, HARRY F. OLSON. (0-486-21769-8)

COMPUTERS, PATTERN, CHAOS AND BEAUTY, CLIFFORD A. PICKOVER. (0-486-41709-3)

AN INTRODUCTION TO INFORMATION THEORY, JOHN R. PIERCE. (0-486-24061-4)

INTRODUCTION TO MATHEMATICAL PHILOSOPHY, BERTRAND RUSSELL. (0-486-27724-0)

HELLENISTIC SCIENCE AND CULTURE IN THE LAST THREE CENTURIES B.C., GEORGE SARTON. (0-486-27740-2)

MATHEMATICIAN’S DELIGHT, W. W. SAWYER. (0-486-46240-4)

SEE EVERY DOVER BOOK IN PRINT AT WWW.DOVERPUBLICATIONS.COM

Copyright © 1977 by Gary Chartrand.

All rights reserved.

This Dover edition, first published in 1985, is an unabridged and corrected republication of the work first published in 1977 by Prindle, Weber & Schmidt, Inc., Boston, under the title Graphs as Mathematical Models.

Library of Congress Cataloging in Publication Data

Chartrand, Gary.

Introductory graph theory.

Reprint. Originally published: Graphs as mathematical models. Boston : Prindle, Weber & Schmidt, c1977.

Includes bibliographies and index.

1. Graph theory. I. Title.

QA166.C453 1985 511’.5 84-18801

9780486134949

Manufactured in the United States by Courier Corporation
24775914
www.doverpublications.com

To Two Model Friends
Sue Steffens Curt Wall

Preface

I have written this book with several objectives in mind:

To teach the reader some of the topics in the youthful and exciting field of graph theory;

To show how graphs are applicable to a wide variety of subjects, both within and outside mathematics;

To increase the student’s knowledge of, and facility with, mathematical proof; and last, but not least,

To have some fun with mathematics.

Courses may be taught from this text that involve all four goals; other courses may minimize or eliminate the rigor of mathematical proof. Thus the text can be used for teaching students at all levels of undergraduate study.

Various versions of the notes which led to this book have been used for teaching courses at universities, colleges, and two-year colleges, the major differences being how the instructor emphasized or de-emphasized proofs. Each of these courses has included Chapters 1−3 and Section 4.1, with careful attention to Chapter 2. The remaining material for these courses was chosen from the later chapters according to the instructor’s tastes.

Recent years have seen increased demand for applications of mathematics. Graph theory has proven to be particularly useful to a large number of rather diverse fields. I have presented several problems throughout the text to illustrate various applications of graphs and graph theory. Appropriate graph theory concepts and results are introduced for the express purpose of “modeling” these problems mathematically. In the process, some of the theory of graphs is developed. The large variety of proofs used in this field can help strengthen the student’s use of mathematical techniques.

Although graphs have numerous significant applications, the nature of the subject lends itself naturally to less serious uses. I have taken advantage of this to insert, now and then, a little humor into the discussion. It is my hope that I do not offend anyone with this use of mathematics.

If the book is to be used in a course which stresses mathematical proofs, then it might be wise for the student to read the Appendix, which discusses sets, relations, functions, wordings of theorems, and proof techniques. Exercises, sections, and chapters which involve a higher degree of mathematical content are starred and probably should be omitted if the course is to de-emphasize proofs. There are other exercises which require some mathematical arguments, and these should probably be omitted as well if the emphasis is strictly on concepts and applications.

Answers, hints, and solutions are provided to selected exercises. Some exercises have no specific answers and are intended as “discussion questions.” Every chapter concludes with Suggestions for Further Reading, and I have briefly indicated the mathematical level of the references. The end of a proof and the end of the Preface are indicated by the symbol ▉. ▉

Acknowledgments

Appreciation is due to several people for their assistance, directly or indirectly, in the writing of this book.

The “flavor” of the book was influenced by my association and friendship with Jim Stewart of Lansing (Michigan) Community College. Shashi Kapoor taught the first course from the original notes, and his success encouraged me to continue writing. Mary Irvin assisted me a great deal with organizing the first draft of the manuscript. To all three of you, many thanks.

Several reviewers at various stages of the book’s development provided valuable suggestions for improvement. It is a pleasure for me to acknowledge John Leonard, Linda Lesniak-Foster, Al Polimeni, Geert Prins, Sy Schuster, Don VanderJagt, and Curt Wall. In addition, I benefited from others who taught from the manuscript, namely Yousef Alavi, Brian Garman, John Roberts, and Jim Williamson.

A special note of thanks to my good friend Marilyn Hass for the continuing interest she expressed in the project.

I am grateful for the cooperation and valuable assistance given me by the staff of Prindle, Weber and Schmidt. The suggestions of David Chelton have been particularly helpful.

Finally, many, many thanks to my wife Marge for her understanding, patience, and excellent typing of the entire manuscript, and to my son Scot who, despite a total lack of interest in graph theory, gave his mother time to type.

Gary Chartrand
Kalamazoo, Michigan

Chapter 1

Mathematical Models

Much of the usefulness and importance of mathematics lies in its ability to treat a variety of situations and problems. The mathematical problems which evolve from the real world have been commonly referred to as “story problems,” “word problems,” and “application problems.” Our goal in this book is to give the real-life problem a mathematical description (or to model it mathematically). Ordinarily, finding a mathematical description is a very complex problem in itself, and there is seldom a unique solution. Indeed, the problem of modeling a real-life situation in a mathematical manner can be so complicated and varied that only the barest introduction is possible at this point.

1.1 Nonmathematical Models

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.

Problem Set 1.1

1. Give three examples of models you have encountered. Indicate some pertinent features of each model and describe a feature each model lacks which would be useful for it to possess.

2. Give an example of a model which is (a) larger than, (b) approximately the same size as the thing it represents.

3. Explain the relationship that radio, television, motion pictures, and the theater have with models. What are some of the pertinent differences in how these media model?

4. List some occupations which deal directly with nonmathematical models.

1.2 Mathematical Models

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:

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₀, S₁, S₂, and S₃ are as follows:

S₀: You are an undergraduate (initial state).

S₁: You look for a job in the business world.

S₂: You travel with your friends.

S₃: You go to graduate school.

Figure 1.1

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:

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².

Hence, we might choose this formula as our model.

Problem Set 1.2

5. Why is the mathematical model described in Example 1.1 likely to be unsatisfactory?

6. What question would you like the mathematical model of Example 1.2 to answer?

7. You take a quart of milk whose temperature is 40° and you place it on a kitchen counter. The temperature in the kitchen is 75°. After one hour, the temperature of the milk has risen to 45°. What mathematical model would represent this situation?

8. In your opinion, what would be a better mathematical model than the given model for the situation described in Example 1.3? Why is yours preferable?

9. Imagine yourself in the position of the college senior of Example 1.4. List the alternatives you would choose and the factors that are important to you in making a decision. By assigning points as in Example 1.4, make a decision. What do you think of this method of making decisions?

10. Give an example of a decision you are likely to make in the near future. Proceed as in Example 1.4 by listing alternatives, indicating important criteria, and assigning points.

11. What is the most important question a mathematical model for Example 1.5 should answer?

12. The following problem is rather common in a beginning calculus course. A square piece of cardboard, 12 centimeters on a side, is to have squares (all of the same size) cut out of its corners. Then its sides will be folded upward to produce a box with no top. What kind of mathematical model would represent this situation? What question would you like the mathematical model to answer?

13. Suppose you have a fair coin; that is, it is equally likely for heads or tails to appear if the coin is flipped. You are approached by a compulsive gambler who states that if you flip this coin four times and heads and tails appear twice each, then he will pay you $11. On the other hand, if you fail, you will pay him only $10. What kind of mathematical model would you identify with this situation? What question would you like the mathematical model to answer?

14. You must pay $10 to play the following game at a carnival. You flip a fair coin three times. When heads comes up the first time, you receive $5. If heads comes up a second time, you receive an additional $7. If heads occurs a third time, you receive yet another $9. Hence, it is possible to receive as much as $5 + $7 + $9 = $21 (for a net profit of $11) or as little as nothing (for a net loss of $10). What kind of mathematical model would you identify with this situation? What question should your model answer for you?

1.3 Graphs

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₁, v₂, v₃, v₄}

together with the relation

R = {(v₁,v₂), (v₁, v₃), (v₂,v₁₎, (v₂,v₃₎, (v₃,v₁), (v₃,v₂), (v₃,v₄), (v₄,v₃)}.

In this case,

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₁,v₂,v₃,v₄} and E = {v₁v₂,v₁v₃,v₂v₃, v₃ v₄}. 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₁v₂ and v₃v₄ 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.

Figure 1.2

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₁ and v₃ are adjacent, but v₁, and v₄ are not adjacent. The vertex v₃ is incident to the edge v₂v₃, but v₄ is not incident to v₂v₃. The edges v₁v₃ and v₃v₄ are adjacent, but v₁v₂ and v₃v₄ are not adjacent.

Problem Set 1.3

15. Draw the graph with vertex set V = {u₁,u₂,u₃,u₄,u₅} and edge set E = {u₁u₂, u₁u₄, u₁u₅, u₂u₃, u₃u₅, u₄u₅}, What is the corresponding irreflexive symmetric relation R on V?

16. Draw a graph G with vertex set V = {u₁, u₂, u₃, u₄, u₅} and edge set E such that ∣E∣is as large as possible. Determine E.

17. If a graph G has order 3, what are the possible sizes for G?

18. What is the maximum possible size of a graph of (a) order 3; (b) order 4; (c) order 5; (d) order n, where n is a positive integer?

19. Does an example exist of a graph of order 3 such that every two vertices are adjacent and every two edges are adjacent? Does such a graph of order 4 exist?

20. Is there a graph G of order five or more such that every vertex of G is incident with at least one edge, but no two edges are adjacent ?

21. Let n ≥ 2 be an integer. If G is a graph of order n, what is the minimum size possible for G (in terms of n) if G contains a vertex which is adjacent to all other vertices of G?

22. Give an example of a graph G of positive size with the property that every vertex is incident with every edge.

23. Give an example of a graph exhibiting the properties that:

every vertex is adjacent to two vertices; and

every edge is adjacent with two edges.

24. If V is a nonempty set, why does it follow that the empty subset of V × V is an irreflexive, symmetric relation on V? Is the relation also transitive?

1.4 Graphs as Mathematical Models

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.

Problem Set 1.4

25. In the graph of Example 1.6, what observation could you expect to make concerning the vertex associated with the “most popular child” in the class? What would you expect to find concerning a vertex associated with a new child in the class? Is it possible that a graph constructed at the beginning of the school year might be different from one constructed at the end of the school year? How could this happen?

*26. Suppose we associate a graph G with a college class in the following manner. The vertices of G correspond to the students in the class, while two vertices of G are adjacent if and only if they correspond to two students having the same major. Can you describe the appearance of G?

27. In Example 1.7, it might be important for two platoons to communicate (indirectly, if not directly). How is it possible to determine by looking at the graph of Example 1.7 whether every two platoons can communicate with each other?

28. What would be an important question to ask concerning the situation described in Example 1.8? Could this question be answered with the aid of the corresponding graph?

29. The Student Council in a certain high school consists of 15 members. Ten different committees in school are made up of Student Council members. Some committees may have only a few members, while others may have many. Some Student Council members may belong to no committees, and other members may belong to several. Give examples of two graphs which describe this situation. Can you think of conditions which may make one graph more useful than the other?

*30. We can generalize Exercise 29 in the following way. Let U be a finite nonempty set, and let S₂, S₂, . . . , Sn be a collection of nonempty subsets of U. Find two examples of graphs which describe this situation.

31. Give an example of a real-life situation which can be represented by a graph. Draw the graph as it may appear.

1.5 Directed Graphs as Mathematical Models

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₁ = {v₁, v₂, v₃, v₄} and E₁ = {(v₁, v₂), (v₂, v₃), (v₃, v₂)}, then we have described a digraph, say D₁. The digraph D₁ 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.

Figure 1.3

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.

Figure 1.4

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.

Problem Set 1.5

32. Draw the digraph whose vertex set is V = {v₁, v₂, v₃, v₄, v₅, v₆} and whose arc set is E = {(v₁, v₃), (v₂, v₃), (v₃, v₄), (v₄, v₁), (v₄, v₃), (v₅, v₆)}.

33. What is the maximum number of arcs possible for a digraph with

3 vertices?

4 vertices?

5 vertices?

n vertices?

34. What property would you expect the relation associated with the digraph of Example 1.9 to have? Describe a simpler digraph than the one given which could model the situation of Example 1.9 equally well.

35. With regard to Example 1.10, what important property would you expect of the traffic pattern? Could this property be determined from the digraph?

36. Give an example of a situation which could be represented better by a digraph than by a graph.

1.6 Networks as Mathematical Models

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 networks, while a network resulting from a digraph is called a directed network. Examples of each are shown in Figure 1.5.

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₁, v₂, v₃},

E = {v₁, v₂, v₁, v₃, v₂, v₃},

and

f = {(v₁, v2, + 1), (v₁v₃, −1), (v₂v₃, −1)},

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

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₁, v₂, v₃},

E = {v₁v₂, v₁v3, v₂v₃},

and

f = {(v₁v₂, 2),(v₁v3, 1),(v₂v₃, 3)},

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

Figure 1.7

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₁, v₂, and v₃ 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₁, and v₂, two days;
between v₁ and v₃, one day;
between v₂ and v₃, three days.

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

Example 1.13

Suppose v₁, v₂, and v₃ are three villages, and suppose there are two roads between v₁ and v₂ , one road between v₁ and v₃, and three roads between v₂ and v₃. 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₁, v₂, v₃, v₄}

and

E = f(v₁, v₂), (v₂, v₃), (v₃, v₂), (v₃, v₃), (v₄, v₄)},

Figure 1.8

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

Problem Set 1.6

37. Give an example (of a type different from Example 1.11) in which a signed graph is an appropriate mathematical model.

38. Why is the situation described in Example 1.13 more conducive to representation by a multigraph than is the situation described in Example 1.12?

39. In Example 1.10 we indicated how a digraph can help describe the traffic pattern of a city having one-way and two-way streets. Explain how a directed network may be more useful than a digraph in describing this situation for a letter carrier.

40. A businessman is driving from Michigan City, Indiana, to O’Hare Airport in Chicago. He reaches an intersection where he has the option of continuing along the main highway, where the traffic increases significantly, or taking a different route which is faster but requires paying a toll of $1.40. Give two possible networks representing the situation, and explain the usefulness of one network over the other.

41. Describe a situation in which the most appropriate mathematical model would have loops.

42. State a definition of “loop-digraph.” Considering the type of relation associated with a loop-digraph, what other term might be more appropriate than “loop-digraph”?

Suggestions for Further Reading

Textbooks providing an introduction to mathematical models often contain a treatment of finite mathematics. One good case in point is the book by Malkevitch and Meyer [4], which also includes a discussion of graphs. Indeed, the book by Kemeny, Snell, and Thompson [2], who first brought finite mathematics to the limelight, includes topics on mathematical models.

There are two texts on graph theory, Ore [5] and Wilson [7], which incorporate several examples of graphs used as mathematical models. The first chapter of Harary [1] contains several examples as well. Advanced treatments of mathematical models of various types are given by Maki and Thompson [3] and by Roberts [6]; however, these require a more extensive background in a variety of mathematical areas.

J F. Harary, Graph Theory. Addison-Wesley, Reading, Mass. (1969).

J. G. Kemeny, J. L. Snell, and G. L. Thompson, Introduction to Finite Mathematics, third edition. Prentice-Hall, Englewood Cliffs, N.J. (1974).

D. P. Maki and M. Thompson, Mathematical Models and Applications. Prentice-Hall, Englewood Cliffs, N.J. (1973).

J. Malkevitch and W. Meyer, Graphs, Models, and Finite Mathematics. Prentice-Hall, Englewood Cliffs, N.J. (1974).

O. Ore, Graphs and Their Uses. Random House, New York, N.Y. (1963).

F. S. Roberts, Discrete Mathematical Models. Prentice-Hall, Englewood Cliffs, N.J. (1976).

R. J. Wilson, Introduction to Graph Theory. Academic Press, New York, N.Y. (1972).

Chapter 2

Elementary Concepts of Graph Theory

To this point, we have introduced several general situations for which graphs or related concepts serve as mathematical models. As we proceed, we shall ask questions pertaining to particular situations and their resultant models. In order to deal with these models in some detail, we must become more familiar with the terminology of graph theory and some of the basic results. We shall investigate these topics in this chapter.

2.1 The Degree of a Vertex

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 Gv, or simply deg v if the graph is clear by context. For the graph G of Figure 2.1, deg v₁ = 1, deg v₂ = 2, deg v₃ = 3, deg v₄ = 2, and deg v₅ = 0.

Figure 2.1

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₁, v₂, . . . , vp, then

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₁, v₂ , . . . , vk. If G contains even vertices as well, then denote these by u₁, u₂, . . . , un. By Theorem 2.1,

where q is the number of edges in G. Since each of the numbers deg u₁, deg u₂, . . . , deg un is even, (deg u₁ + deg u₂ + · · · + deg un) is even, so we have

However, each of the numbers deg v₁, deg v₂, . . . , deg vk 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₁ + deg v₂ + · · · + deg uk) = 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 Kp. Five complete graphs are shown in Figure 2.2.

Figure 2.2

Problem Set 2.1

1. For the graph G of Figure 2.3, determine deg vi for i = 1, 2, . . . , 8 and determine its order p and size q. Then, illustrate Theorem 2.1 by verifying that deg vi = 2q.

Figure 2.3

2. Show that a graph G cannot exist with vertices of degrees 2, 3, 3, 4, 4, and 5.

3. Show that a graph G cannot exist with vertices of degrees 2, 3, 4, 4, and 5.

*4. Show that a graph G cannot exist with vertices of degrees 1, 3, 3, and 3.

5. Suppose we know the degrees of the vertices of a graph G. Is it possible to determine the order and size of G? Explain.

*6. Suppose we know the order and size of a graph G. Is it possible to determine the degrees of the vertices of G? Explain

7. Give an example of a graph

having no odd vertices.

having no even vertices.

having exactly one odd vertex.

having exactly one even vertex.

having exactly two odd vertices.

having exactly two even vertices.

8. Let p and n be integers such that n is even and satisfies 0 ≤ n < p. Give an example of a graph G of order p containing exactly n odd vertices. Is it necessary to stipulate that n is even?

9. If G is a (p, q) r-regular graph, express q in terms of p and r. What is q if G = Kp?

10. Give an example of a

0-regular graph which is not complete.

1-regular graph which is not complete.

2-regular graph which is not complete.

3-regular graph which is not complete.

11. Let m and n be nonnegative integers such that m ≠ n. Find an example of a graph G such that each vertex has degree m or n. (Note: Your example must be general. Do not assign specific values to m and n.)

*12. A graph G of order p(≥2) is called perfect if no two of its vertices have equal degrees. Prove that “no graph is perfect.” If we replace “(≥2)” by “(≥1),” does the conclusion change?

*13. Suppose you and your husband attended a party with three other married couples. Several handshakes took place. No one shook hands with himself (or herself) or with his (or her) spouse, and no one shook hands with the same person more than once. After all the handshaking was completed, suppose you asked each person, including your husband, how many hands he or she had shaken. Each person gave a different answer.

How many hands did you shake?

How many hands did your husband shake?

2.2 Isomorphic Graphs

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₁ and G₂ are two equal graphs which are models of two situations, then there is something basically similar about the two situations.

Intuitively, two graphs G₁ and G₂ are the same if it is possible to redraw one of them, say G₂, so it appears identical to G₁. For example, the graphs G₁ and G₂ 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₁ and G₂ be two graphs. By an isomorphism from G₁ to G₂ we mean a one-to-one mapping φ : V(G₁) → V(G₂) from V(G₁) onto V(G₂) such that two vertices u₁ and v₁ are adjacent in G₁ if and only if the vertices φ(u₁) and φ(v₁) are adjacent in G₂. We then say that G₁ and G₂ are isomorphic if an isomorphism exists from G₁ to G₂. If φ is an isomorphism from G₁ to G₂, then the inverse mapping φ⁻¹ (see Exercise A.25, page 255) from V(G₂) to V(G₁) also satisfies the definition of isomorphism. If G₁ and G₂ are isomorphic graphs, we can say that G₁ is isomorphic to G₂ and that G₂ is isomorphic to G₁.

Figure 2.4

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₁ is isomorphic to G₂; that is, suppose φ is an isomorphism from G₁ to G₂. Define the inverse −mapping φ⁻¹: V(G₂) → V(G₁₎ by φ⁻¹(v₂) = v₁ if φ(v₁) = v₂. By Exercise A.25, φ⁻¹ is a one-to-one mapping from V(G₂) onto V(G₁). Suppose u₂, v₂ ∊ V(G₂), and φ⁻¹ (u₂) = u₁ and φ⁻¹(v₂) = v₁. Then φ(u₁) = u₂ and φ(v₁) = v₂. From these last equalities, u₂ and v₂ are adjacent if and only if φ(u₁) and φ(v₁) are adjacent, and since G₁ is isomorphic to G₂, φ(u₁) and φ(v₁) are adjacent if and only if u₁ = φ⁻¹(u₂) and v₁ = φ⁻¹(v₂) are adjacent. Therefore, u₂ and v₂ are adjacent if and only if φ⁻¹(u₂) and φ⁻¹(v₂) are adjacent. This shows that G₂ is isomorphic to G₁, i.e. “is isomorphic to” is a symmetric relation.

We still must show that the relation is transitive. Suppose that G₁ is isomorphic to G₂ and that G₂ is isomorphic to G₃. Hence there exist isomorphisms α: V(G₁) → V(G₂) and β: V(G₂) → V(G₃). Consider the composite mapping β ⃘ α. By Theorems A.4 and A.5 (page 254), β ⃘ α is a one-to-one mapping from V(G₁) onto V(G₃). Let u₁, v₁ ∊ V(G₁). Suppose that α(u₁) = u₂ and α(v₁) = v₂, and that β(u₂) = u₃ and β(v₂) = v₃. Since α and β are isomorphisms, u₁ and v₁ are adjacent if and only if α(u₁) = u₂ and α(v₁) = v₂ are adjacent; and u₂ and v₂ are adjacent if and only if β(u₂) = u₃ and β(v₂) = v₃ are adjacent. Thus, u₁ and v₁ are adjacent if and only if u₃ = (β ⃘ α)(u₁) and v₃ = (β ⃘ α)(v₁) are adjacent. This completes the proof that β ⃘ α is an isomorphism. Hence, G₁ is isomorphic to G₃. ▋

By Theorem A.2 (page 248), 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₁ and G₂ are isomorphic graphs, then, by definition, there exists a one-to-one mapping φ from V(G₁) onto V(G₂). This implies that V(G₁) and V(G₂) have the same number of elements; that is, G₁ and G₂ have the same order. Let u₁ and v₁ be two vertices of G₁. and suppose that φ(u₁) = u₂ and φ(v₁) = v₂. Then u₁ and v₁ are adjacent in G₁ if and only if u₂ and v₂ are adjacent in G₂, or in other words, u₁v₁ is an edge of G₁ if and only if u₂v₂ is an edge of G₂. This implies that G₁ and G₂ 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.

Figure 2.5

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

A very useful necessary condition for a graph G₁ to be isomorphic to a graph G₂ is presented next.

Theorem 2.4

If G₁ and G₂ are isomorphic graphs, then the degrees of the vertices of G₁ are exactly the degrees of the vertices of G₂.

Proof

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

Since deg u = n, the graph G₁ contains vertices u₁, u₂, . . . , un which are adjacent to u, while every other vertex of G₁ is not adjacent to u. Let φ(ui) = vi for i = 1, 2 , . . . , n. Then v is adjacent to each of the vertices v₁, v₂, . . . , vn, since φ is an isomorphism. Furthermore, these are the only vertices adjacent to v, since u is adjacent to x in G₁ if and only if v is adjacent to φ(x) in G₂. Thus, deg v = n.

Because a vertex of G₁ and its image vertex of G₂ 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₁ and G₂ of Figure 2.5 are not isomorphic.) On the other hand, if the degrees of the vertices of a graph G₁ and the degrees of the vertices of a graph G₂ are not the same, then by Theorem 2.4, G₁ and G₂ are not isomorphic.

It follows that there is only one graph of order one (necessarily having size zero); that is, if G₁ and G₂ 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.

Figure 2.6

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₁, S₂, . . . , Sk be a partition of S into k subsets. Then at least one subset Si, 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.

Problem Set 2.2

14. Show that the graphs G₁ and G₂ of Figure 2.4 are isomorphic by redrawing G₂ in such a way that it appears exactly like G₁.

15.

Show that the graphs G₁ and G₂ of Figure 2.4 are isomorphic by showing that an isomorphism φ exists from G₁ to G₂.

Show that the graphs G₁ and G₂ of Figure 2.4 are isomorphic by showing that an isomorphism 0 exists from G₂ to G₁.

16. Show that the graphs F₁ and F₂ of Figure 2.7 are isomorphic by proving the existence of an isomorphism from F₁ to F₂ or of an isomorphism from F₂ to F₁.

Figure 2.7

17. Let G₁ be a graph whose vertices have degrees 2, 2, 3, 3, 4, and 4, and let G₂ be a graph whose vertices have degrees 2, 3, 3, 3, 3, and 4. Can G₁ and G₂ be isomorphic? Explain.

18. Show that no two graphs of Figure 2.6 are isomorphic.

*19. Show that the (8, 8) graphs F₁ and F₂ of Figure 2.8 are not isomorphic.

Figure 2.8

20. The degrees of the vertices of the non-isomorphic graphs F₁ and F₂ of Figure 2.8 are 2, 2, 2, 2, 2, 2, 2, and 2. Does an (8, 8) graph F₃ exist with that same property, such that F₃ is isomorphic to neither F₁ nor F₂? Explain.

21. Show that the graph G₃ of Figure 2.9 (page 40) is isomorphic to exactly one of the graphs of Figure 2.5.

22. Give an example of two non-isomorphic (4, 2) graphs. Verify that these graphs are not isomorphic.

*23. Prove the Pigeonhole Principle. (Hint: Try a proof by contradiction.)

Figure 2.9

*24. Let G be a graph of order 9 such that each vertex of G has degree 5 or 6. Prove that at least five vertices of G have degree 6 or at least six vertices of G have degree 5.

*25. Let G₁, G₂, and G₃ be any three (4, 2) graphs. Prove that at least two of these graphs are isomorphic.

*26. Which pairs of graphs in Figure 2.10 are isomorphic and which pairs are not isomorphic? (Hint: Try redrawing them.)

Figure 2.10

2.3 Connected Graphs

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.

Figure 2.11

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₃, v₃v₂, v₂, v₂v₆, v₆. v₆v₃, v3, v₃v₄, v₄, v₄v₅, v₅, v₅v₄, v₄ is a v₃−v₄ walk in the graph G of Figure 2.11. Observe that the edge v₄v₅ 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₃, v₂, v₆, v₃, v₄, v₅, v₄.

A u−v trail in a graph is a u−v walk which does not repeat any edge. The v₃−v₄ walk described above is not a v₃−v₄ trail; however, v₃, v₂, v₆, v₃, v₄ is a v₃−v₄ 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₃, v₅, v₄ is a v₃−v₄ path.

Two vertices u and vin 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.

Figure 2.12

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₁ v₂, v₃, v₅, v₂, v₆, v₁ is a circuit but is not a cycle, while v₂, v₄, v₃, v₅, v₂ 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₁, v₂, v₅, v₃, v₂, v₆ is a trail in the graph G of Figure 2.13. If we define the subgraph H of G by V(H) = {v1, v₂, v₅, v₃, v₆} and E(H) = {v₁,v₂, v₂v5, v₅ v₃, v₃ v₂, v₂ v₆}, 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.

Figure 2.13

Problem Set 2.3

27. Give an example of a disconnected graph with four components where each component is complete.

28. Give an example of a disconnected graph with three components where no two components are isomorphic.

29. Give an example of a disconnected graph with three components where every two components are isomorphic.

30. Let n and p be integers such that 1 ≤ n ≤ p. Provide an example of a graph of order p having n components.

31. Is it possible for a graph to have more components than vertices? Explain.

32. Let G be a graph of order 13 containing three components. Show that at least one component of G has at least five vertices.

*33. Let G be a graph of even order p (i.e., p = 2n for some positive integer n) such that G has two complete components. Prove that the minimum size possible for G is q = (p² − 2p)/4. (Hint: Try a calculus argument.) If G has this size, what does G look like?

*34. Let G be a graph. Define a relation R on V(G) as follows: u R v if u = v or if uv ∊ E(G). Suppose R is an equivalence relation. Describe G.

*35. Prove that a graph G is connected if and only if for every two vertices u and v of G, there exists a u−v walk in G.

*36. Let G₁, and G₂ be isomorphic graphs. Prove that if G, is connected, then G₂ is connected.

*37. Let G be a graph of order p (≥ 2), and suppose that for every vertex v of G, deg v ≥ (p − 1)/2. Prove that G is connected. (Hint : Try a proof by contradiction. To begin, assume that deg v ≥ (p − 1)/2 for every vertex v of G and that G is disconnected. Since G is disconnected, G has two or more components. What can be said about the number of vertices in each component?)

*38. Let G be a graph of order p (≥ 2), and suppose that for every vertex v of G, deg v ≥ (p − 2)/2. Show that G need not be connected if p is even (see Exercise 37).

39. In the graph G of Figure 2.14, give an example of a circuit C which is not a cycle. Describe the subgraph H of G whose vertices and edges belong to C.

Figure 2.14

40. In the graph G of Figure 2.14, give an example of

a trail which is not a path;

a path;

a cycle.

*41. Prove that every u−v trail contains a u−v path.

*42. Prove that every circuit contains a cycle.

43. Consider the sequence of vertices v1, v₂, v₃, v₄, v₅, v₂, v₁ of the graph G of Figure 2.13. Is this a circuit, a cycle, or neither? Explain.

*44. Let G be a graph, and let R denote the relation “is connected to” on the set V(G). Show that R is an equivalence relation. Determine the equivalence classes.

2.4 Cut- Vertices and Bridges

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₃ 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₄ of the graph G in Figure 2.15 is a bridge, but no other edge of that graph is a bridge.

Figure 2.15

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₁ be any two vertices of G − e; we show that G − e contains a u₁−v₁ path. Since G is connected, there is a u₁−v₁ 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₁ in G − e. Suppose the edge e lies on P. Then the path P can be expressed as u1, . . . , u, v, . . . , v₁, or u₁, . . . , v, u, . . . , v₁. In the first case, u₁ is connected to u and v is connected to v₁ in G − e, and in the second case, u₁ is connected to v and u is connected to v₁. 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₁ is connected to v₁. 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. ▋

Problem Set 2.4

45. In the graph G of Figure 2.16 (page 48), determine the cut-vertices and the bridges of G.

46. Give an example of a connected graph G containing a vertex v such that G − v has four components.

Figure 2.16

47. Let G be a graph of order 11 and let e be a bridge of G and v be a vertex of G.

Show that there exists a component of G − e containing at least six vertices.

Show that there need not exist a component of G − v containing at least six vertices.

*48. Let G be a connected graph containing only even vertices. Prove that G cannot contain a bridge. (Note: In any negative-type result, a good proof technique to try is proof by contradiction.)

49. Let G be a connected graph containing only even vertices. Show that it is possible for G to contain cut-vertices.

50. By Theorem 2.5, if e is an edge of a connected graph G such that e does not lie on any cycle of G, then e must be a bridge of G. Show that if v is a vertex of G such that v does not lie on any cycle of G, then v need not be a cut-vertex of G.

51. Is Theorem 2.5 still true if the word “cycle” is replaced by “circuit”? Verify your answer.

52. Restate Theorem 2.5 using the phrase “necessary and sufficient.”

53. Give an example of a connected, 3-regular graph containing a bridge.

54. Give an example of a connected graph containing more bridges than cut-vertices.

55. Give an example of a connected graph containing more cut-vertices than bridges.

56. One possible definition of a cut-vertex of a disconnected graph is the following: A vertex v of a disconnected graph G is a cut-vertex if v is a cut-vertex of a component of G. Can you give another, yet equivalent, definition? Give two (equivalent) definitions of a bridge in a disconnected graph.

57. Give an example of a graph of order 5 such that every edge is a bridge.

*58. Let G be a connected graph, and let u, v, and w be three vertices of G. Suppose that every u−w path contains v. What property does v have? Prove your assertion.

*59. If G is a connected graph not isomorphic to K₂, and if e is a bridge of G, show that e is incident with a cut-vertex in G.

*60. Determine whether the following statement is true: If G is a connected graph with a cut-vertex, then G has a bridge. If true, give a proof; if false, give an example of a connected graph with a cut-vertex and no bridges.

Suggestions for Further Reading

In this chapter we have taken a brief look at some of the basic concepts of graph theory. We shall encounter several more as we continue through the text; however, we shall not investigate any particular topic in great depth. There are several readable texts that present introductory accounts of the mathematical theory of graphs. Three such examples are books by Wilson [3], Harary [2], and Behzad, Chartrand and Lesniak-Foster [1]. The first of these is the most elementary of the three; the latter two discuss a larger variety of graph-theoretic concepts and problems.

M. Behzad, G. Chartrand, and L. Lesniak-Foster, Graphs & Digraphs. Wadsworth International Group, Belmont, CA (1979).

F. Harary, Graph Theory. Addison-Wesley, Reading, Mass. (1969).

R. J. Wilson, Introduction to Graph Theory. Academic Press, New York (1972).

Chapter 3

Transportation Problems

We have introduced and discussed some of the basic terminology related to graphs, and we have seen a few examples of how graphs may serve as mathematical models representing certain situations. In this chapter we begin our investigation of problems which can be solved with the aid of graphs used as mathematical models. The first collection of problems we consider belongs to the general area of transportation problems.

3.1 The Königsberg Bridge Problem: An Introduction to Eulerian Graphs

Probably the earliest example of a problem making use of graphs (or related concepts) as mathematical models occurred in 1736. This is the famous Königsberg Bridge Problem. We quote from Newman [6]:

The Königsberg Bridge Problem

IN THE TOWN of Königsberg there were in the 18th century seven bridges which crossed the river Pregel. They connected two islands in the river with each other and with opposite banks. The townsfolk had long amused themselves with this problem: Is it possible to cross the seven bridges in a continuous walk without recrossing any of them?

Figure 3.1 shows a schematic diagram of Königsberg, with the land areas denoted by A, B, C, and D.

The situation in Königsberg can be conveniently represented by a multigraph (see p. 21), as shown in Figure 3.2. The vertex set corresponds to the land areas and each two vertices are joined by a number of edges equal to the number of bridges joining the corresponding land areas.

Figure 3.1

The Königsberg Bridge Problem is essentially the problem of determining whether the multigraph M of Figure 3.2 has a trail (possibly a circuit) containing all its edges. You might use a trial-and-error method, and you would probably reach the conclusion that no such trail exists. However, how do you prove that no such trail exists? We present a proof of this fact.

Figure 3.2

Theorem 3.1

Solution of the Königsberg Bridge Problem

The multigraph M of Figure 3.2 has no trail containing all edges of M.

Proof

Notice first that this theorem is negative in nature, since we wish to show that M does not have a certain kind of trail. Therefore, it is natural to attempt a proof by contradiction, as follows. Suppose the multigraph M of Figure 3.2 does have a trail, say P, which contains all edges of M. Then P begins at one of the four vertices A, B, C, or D and ends at one of A, B, C, or D (the same vertex from which P started if P is a circuit). Now there are at least two vertices among A, B, C, and D such that P neither begins nor ends at that vertex. Hence there is at least one vertex among B, C, and D at which P neither begins nor ends. Let us denote such a vertex by v.

Notice that each of the vertices B, C, and D has degree 3. Thus, after some edge on P enters vertex v for the first time and some other edge on P leaves vertex v, there is exactly one edge incident with v which does not yet belong to P. Now v must be entered along trail P once again via the edge incident with v which was not yet used. However, upon arriving at v the second time, we find no edges remaining to exit, so that P must terminate at v. This is impossible since P does not end at v. Hence, no such trail P exists, producing the desired contradiction. ▋

As a note to the preceding theorem and proof, we repeat the statement that any theorem claiming the nonexistence of some quantity, or, more generally, having some negative-sounding aspect to it, is commonly proved by a contradiction argument.

The Königsberg Bridge Problem was initially solved by the famous Swiss mathematician Leonhard Euler (1707–1783). The type of trail sought in the Königsberg Bridge Problem has given rise, in a very natural way, to a class of graphs (actually multigraphs) bearing the name of Euler.

A circuit containing all the vertices and edges of a multigraph M is called an eulerian circuit in M. A graph containing an eulerian circuit is called an eulerian graph, while a multigraph containing an eulerian circuit is an eulerian multigraph. The graph in Figure 3.3 is eulerian; C: u₁, u₂, u₃, u₄, u₅, u₃, u₆, u₇, u₁, u₃, u₇, u₂, u₆, u₁ is one eulerian circuit.

Figure 3.3

The following theorem provides a very simple solution to the problem of determining which graphs and multigraphs are eulerian.

Theorem 3.2

A multigraph G is eulerian if and only if G is connected. and every vertex of G is even.

The proof of Theorem 3.2, although not extremely difficult, is somewhat lengthy. Thus, before giving the proof, we illustrate the procedure used on the eulerian graph G of Figure 3.3. Consider the vertex u₁, say. We begin a trail P at u₁ and continue the trail as long as possible. If we are fortunate, P will be an eulerian circuit; however, it may happen that we obtain the circuit P: u₁, u₂, u₃, u₆, u₇, u₁, u₃, u₇, u₂, u₆, u₁. In this case, P is not an eulerian circuit, since it does not contain all edges and vertices of G. However, u₃ is a vertex of P that is incident with edges not on P. We now begin a trail P₁, at u₃ which contains edges not belonging to P. If we continue P₁ as long as we can, one possible choice of P₁ would be u₃, u₄, u₅, u₃. We now insert P₁ into P at the first place where u₃ is encountered, obtaining u1, u2, u3, u₄, u₅, u₃, u₆, u₇, u₁, u₁, u₃, u₇, u₂, u₆, u₁, which is an eulerian circuit.

Proof of Theorem 3.2

Suppose G is an eulerian multigraph. Then G contains an eulerian circuit C, which begins and ends, say, at the vertex v. Since C contains all vertices of G, every two vertices of G are joined by a trail (and therefore by a path), so that G is connected. We now show that every vertex of G is even. First we consider a vertex u different from v. Since u is neither the first nor the last vertex of C, each time u is encountered it is entered via some edge and exited via another edge; hence, each occurrence of u in C increases the degree of u by two. Thus, u has even degree. In the case of the vertex v, each occurrence of v except the first and the last contributes two to its degree, while the initial and final occurrences of v in C contribute one each to the degree of v. Therefore, every vertex of G has even degree.

We now consider the converse statement. Assume that G is a connected multigraph and every vertex in G is even. We show that G is eulerian. Select a vertex v of G, and begin a trail P at v. We continue this trail as long as possible until we reach a vertex w such that the only edges incident with w already belong to P; hence, P cannot be continued, and we must stop. We claim that w = v. To establish this claim, suppose that w ≠ v. On each occasion that w is encountered prior to the last time, we use one edge to enter w and another edge to exit from w. When w is encountered for the final time on P, only one edge is used—namely. to enter w. Hence, an odd number of edges incident with w appears on P. However, since w has even degree, there must be at least one edge incident with w that does not belong to P. This implies that P can be continued and therefore cannot terminate at w, if w # v. We conclude that w = v, and P is actually a circuit. If the circuit P contains all the edges of G, then P is an eulerian circuit of G and G is an eulerian multigraph.

Suppose the circuit P does not contain all the edges of G. Since G is connected, there must be at least one vertex u on P that is incident with edges not on P. Remove the edges of P from G and consider the resulting multigraph H. Since P does not contain all the edges of G, the multigraph H has edges. Furthermore, every vertex belonging to P is incident with an even number of edges of P: hence, every vertex in H has even degree. Let H₁ be the component of H containing the vertex u. If we begin a trail P₁, in H₁ at u and continue this trail as long as possible, then, as before, P₁ must end at u (that is, P₁ must be a circuit). Now it is possible to form a circuit C₁ of G, beginning and ending at v, which has more edges than P. We do this by taking the circuit P and inserting the circuit P₁ at a place where u occurs.

If C₁ contains all the edges of G, then C₁ is an eulerian circuit and G is an eulerian multigraph. If C₁ does not contain all the edges of G. then we may continue the above procedure until we finally obtain an eulerian circuit of G. ▋

We now consider an analogous concept. If a graph G has a trail, not a circuit, containing all vertices and edges of G, then G is called a traversable graph and the trail is called an eulerian trail. Figure 3.4 shows a traversable graph and P: v₁,v₂, v₄, v₃, v₂, v₅, v₄ is an eulerian trail.

Figure 3.4

The following theorem indicates precisely which graphs are traversable.

Theorem 3.3

A multigraph G is traversable if and only if G is connected and has exactly two odd vertices. Furthermore, any eulerian trail of G begins at one of the odd vertices and ends at the other odd vertex.

We can now see that the multigraph M of Figure 3.2 is neither eulerian nor traversable, so there is no trail in M containing all edges of M. This fact gives us another solution of the Königsberg Bridge Problem.

An interesting property of eulerian and traversable multigraphs is that once the vertices have been drawn, we can draw the edges in one “continuous” motion. In other words, the edges of a connected multigraph can be drawn “without lifting the pencil from the paper” provided the number of odd vertices is zero or two.

Eulerian and traversable graphs and multigraphs find numerous applications in solving mazes, puzzles, and similar problems. We give two such examples now.

Example 3.1

Figure 3.5 shows the floor plan of a house with various doorways leading between rooms, and between several rooms and the outside. Is it possible to start someplace (either in a room or outdoors) and walk through every doorway once and only once?

We use a multigraph as a mathematical model of this situation. We first associate a vertex with each room and a vertex with the outdoors. Every two vertices are joined by a number of edges equal to the number of doorways between the corresponding rooms (or the room and outside). The answer to the question now depends on whether the multigraph is eulerian, traversable, or neither. We see, however, that vertices B, D, E, and 0 are odd, so the multigraph of Figure 3.5 is neither eulerian nor traversable. Hence, it is not possible to walk through every doorway once and only once.

Figure 3.5

Example 3.2

Suppose you hold a summer job as a highway inspector. Among your responsibilities, you must periodically drive along the several highways shown schematically in Figure 3.6 and inspect the roads for debris and possible repairs. If you live in town A, is it possible to find a round trip, beginning and ending at A, which takes you over each section of highway exactly once? If you were to move to town B, would it be possible to find such a round trip beginning and ending at B?

Figure 3.6

To solve this problem, we need only regard the highways as a graph. Observe that the graph of Figure 3.6 is connected and every vertex is even. Therefore, the graph is eulerian and contains an eulerian circuit C. The circuit C contains every edge of the graph exactly once, so a round trip must exist containing each section of highway exactly once. Since a circuit may begin at any vertex of the circuit, there are round trips beginning at either A or B. (A round trip beginning at B, however, will pass through B at some intermediate time before coming to an end.)

Problem Set 3.1

1. Classify the graphs in Figure 3.7 as eulerian, traversable, or neither.

Figure 3.7

2. Give an example of a graph of order 10 which is

eulerian.

traversable.

neither eulerian nor traversable.

3. Let G₁ and G₂ be two eulerian graphs with no vertices in common. Let v₁ be a vertex of G₁ and let v₂ be a vertex of G₂. Let G be a graph consisting of G₁ and G₂, together with the edge v₁v₂. What can be said about G?

4.

Show that if M is a traversable multigraph, then an eulerian multigraph can be constructed from M by the addition of a single edge.

Would the result in (a) be true if the two occurrences of the word “multigraph” were replaced by “graph”?

Would the result in (a) be true if the word “addition” were replaced by “deletion”?

*5. We know that a connected multigraph with no odd vertices contains an eulerian circuit, and a connected multigraph with exactly two odd vertices contains an eulerian trail. Try to determine what special property is exhibited by a connected multigraph with exactly four odd vertices. Try to prove your answer.

*6. Prove Theorem 3.3.

7. Figure 3.8 shows a diagram of the mystical town of Libb, with its three islands and many fabled bridges. Is it possible to walk through the town of Libb and cross each bridge once and only once? If so, show how such a walk can be made.

Figure 3.8

8. Figure 3.9 gives a (rather loosely drawn) map of the famous Snuff Islands off the coast of Zambesi. Boat routes for scenic tours are indicated on the map by dashed lines. Is it possible to make a round trip from Zambesi which follows each and every boat route exactly once?

Figure 3.9

9. Suppose there is a group of four islands where a single boat route exists between each two islands. Is it possible to take a trip (not necessarily a round trip) that uses each boat route exactly once?

10. Figure 3.10 (page 64) shows a blueprint of a house. Can a person walk through each doorway of this house once and only once? If so, show how it can be done.

Figure 3.10

11. The scene is the estate of the well-to-do billionaire Count Van Diamond. He has just been murdered, and James Bomb, the internationally known detective, former notary public, current assistant manager of Chicken Delight, and part-time graph theorist, has been called in to investigate. The butler claims he saw the gardener enter the pool room (where the murder took place) and then, shortly after, leave that room by the same door. The gardener, however, says that he cannot be the man whom the butler saw, for he entered the house, went through each door exactly once, and then left the house. James Bomb checks the floor plan (given in Figure 3.11). Within a matter of hours, he declares the case solved. Who killed the Count?

Figure 3.11

12. A letter carrier is responsible for delivering mail to houses on both sides of the streets shown in Figure 3.12. If the letter carrier does not keep crossing a street back and forth to get to houses on both sides of a street, it will be necessary for her to walk along a street at least twice, once on each side, to deliver the mail. Is it possible for the letter carrier to construct a round trip so that she walks on each side of every street exactly once?

Figure 3.12

*13. Does the solution of Exercise 3.12 depend significantly on the street diagram? Does this result suggest a theorem to you? If so, try to state the result and supply a proof.

14. Figure 3.13 is a diagram of the “Hall of Mirrors” at an amusement park. After each visitor passes through the entrance door, and through each door thereafter, the door automatically shuts and locks behind him. Assuming that you can eventually find your way out of any room if not all the doors in the room are locked, determine whether it is always possible to escape from the Hall of Mirrors, or whether you might become trapped in some room of the Hall of Mirrors . . . forever.

Figure 3.13

* 15. Prove that a graph G is eulerian if and only if G is connected and its edge set can be partitioned into cycles.

3.2 The Salesman’s Problem: An Introduction to Hamiltonian Graphs

The Salesman’s Problem

SUPPOSE A SALESMAN’S TERRITORY includes several cities with highways connecting certain pairs of these cities. His job requires him to visit each city personally. Is it possible for him to schedule a round trip by car enabling him to visit each specified city exactly once?

We can represent this “transportation system” by a graph G whose vertices correspond to the cities, and such that two vertices are joined by an edge if and only if a highway connects the corresponding cities and does not pass through any other specified city. The solution to the problem depends on whether G has a cycle containing every vertex of G. (Note the difference between this problem and the problem in Section 3.1 of determining whether G has a circuit containing every vertex and edge of G.)

An important concept is suggested by this problem. We call a graph G hamiltonian if a cycle exists in G containing every vertex of G. A cycle containing all vertices of G is referred to as a hamiltonian cycle. Thus, a hamiltonian graph is a graph containing a hamiltonian cycle.

The graph G₁ of Figure 3.14 is hamiltonian, while G₂ is not hamiltonian. Graph G₁ is hamiltonian because it contains a hamiltonian cycle; for example, u₁, u₂, u₅, u₄, u₃, u₁ is a hamiltonian cycle. In order to show that G₂ is not hamiltonian, we give a proof by contradiction. Suppose, then, that G₂ is hamiltonian. Therefore, G₂ contains a hamiltonian cycle C. Now C contains every vertex of G₂; hence, C contains v₂, v₃, and v₄. Each of v₂, v₃, and v₄ has degree two, so C must contain the two edges incident with each of v₂, v₃, and v₄. This means, for example, that C contains all three edges v₁v₂, v₁v₃, and v₁v₄. However, any cycle can contain only two edges incident with a vertex on the cycle. Therefore, G₂ cannot contain a hamiltonian cycle, which contradicts the assumption that G₂ is hamiltonian.

Figure 3.14

It should now be apparent that the solution of any Salesman Problem depends on whether the associated graph is hamiltonian. Unfortunately, no one has yet found a convenient method for determining which graphs are hamiltonian. For the most part, each graph must be considered individually. However, some conditions have been developed which imply that the graph under consideration is necessarily hamiltonian. We present one of these results now.

Theorem 3.4

If G is a graph of order p (≥ 3) such that deg v ≥ p/2 for every vertex v of G, then G is hamiltonian.

Proof

If G has order p = 3 and deg v ≥ 3/2 for every vertex v of G, then deg v = 2 and G = K₃ (Figure 2.2, page 30). Therefore, the result is true for p = 3. We now assume p ≥ 4. Among all the paths in G, let P be one of those paths with the greatest number of vertices. Suppose P : u₁, u₂, . . . , uk is this path (see Figure 3.15).

Figure 3.15

Since no path in G has more vertices than P, every vertex adjacent with u₁ must belong to P. Also, every vertex adjacent to uk must belong to P. Since u₁is adjacent to at least p/2 vertices, all on P, it follows that P must contain at least 1 + p/2 vertices.

Now, there must be some vertex ui on P, where 2 ≤i ≤k, such that u₁ is adjacent to u₁and uk is adjacent to ui − ₁. If this were not the case, then for each vertex ui adjacent to u1, the vertex ui−1 would not be adjacent to uk. However, since there are at least p/2 vertices ui adjacent to u₁, there would be at least p/2 vertices ui−1 not adjacent to uk. Therefore, deg uk ≤ (p − 1) − p/2 < p/2, which is impossible since deg uk ≥ p/2. Hence there is a vertex ui on P such that u₁ui and ukui−1 are both edges of G (see Figure 3.16). It now follows that there is a cycle C:u₁, ui, ui+1, . . . ,uk, ui−1, ui−2, . . . , u₁ containing all the vertices of P.

Figure 3.16

If all vertices of G belong to C, then C is a hamiltonian cycle and G is a hamiltonian graph. Suppose there is a vertex w of G that does not belong to C. Since C contains at least 1 + p/2 vertices, fewer than p/2 vertices of G do not lie on C. Since deg w ≥ p/2, the vertex w must be adjacent to some vertex uj of C. However, the edge wuj and the cycle C produce a path having one more vertex than P, which cannot occur since P has the greatest number of vertices. This contradiction implies that C contains all vertices of G, so that G is hamiltonian. ▋

While the condition that deg v ≥ p/2 for every vertex v of a graph G is sufficient for G to be hamiltonian, it is certainly not necessary. For example, G may be simply a cycle, in which case every vertex has degree two, but G is hamiltonian.

We should mention here how “hamiltonian” graphs got their name. It is said that the famous Irish mathematician Sir William Rowan Hamilton (1805–1865) invented a game which involved a regular solid dodecahedron (an object having 20 vertices, 30 edges, and 12 faces, this last property making it ideal as a desk-calendar paperweight). Hamilton labeled each vertex of the dodecahedron with the name of a well-known city. The object of the game was for the player to travel “Around the World” by determining a round trip which included all the cities exactly once, with the added restriction that it is possible to travel from one city to another only if an edge exists between the corresponding vertices. Figure 3.17 shows the graph representing this problem, made up of the vertices and edges of the dodecahedron. Thus, the object of Hamilton’s game is to find a “hamiltonian” cycle in the graph of the dodecahedron.

Figure 3.17

There are other puzzles whose solution can involve hamiltonian graphs. We consider one of these.

Example 3.3

Figure 3.18 shows a 6-by-6 maze (consisting of 36 squares). Is it possible to start at one of the squares, say the one in the upper left-hand corner, proceed to each square exactly once, and return to the starting square? This situation can be represented by the graph G in Figure 3.18. The vertices of G correspond to the squares of the maze and two vertices are joined by an edge if and only if we can move directly from one of the corresponding squares to the other. The solution to the maze depends on whether the graph G is hamiltonian, although the problem is probably easier to solve, in this case, without the aid of graphs. The answer to the question is affirmative, of course, with one solution shown by the dashed line in Figure 3.18.

Figure 3.18

We conclude this section by mentioning a problem closely related to the Salesman’s Problem. Suppose a traveling salesman is to visit certain cities on a trip and then return home. What is the least expensive such trip the salesman can make? This problem is called the Traveling Salesman Problem, and has importance in the area of operations research. (Operations research applies mathematical theories and techniques to complex management problems.) The situation can be represented by an undirected network G whose vertices correspond to the various cities. Every two vertices are joined by an edge, and each edge is given a numerical value equal to the cost of traveling between the corresponding two cities. If we define the value of a hamiltonian cycle of G to be the sum of the values of its edges, then the problem is to find a hamiltonian cycle in G having minimum value. However, despite the simplicity of this statement of the Traveling Salesman Problem, no efficient solution has yet been found.

Problem Set 3.2

16. Determine which graphs in Figure 3.19 are hamiltonian.

Figure 3.19

17. Give an example of a graph of order 10 which is

hamiltonian

not hamiltonian.

18. Show that the graph G of Figure 3.20 is not hamiltonian.

Figure 3.20

19. Show that the graph of a geometric cube is hamiltonian.

20. Learn what the geometric figure called an icosahedron is. Then show that the graph of an icosahedron is hamiltonian.

21. Show that Theorem 3.4 is no longer true if the number p/2 is replaced by (p − 1)/2.

*22. Let G be a graph. A path P in G is called a hamiltonian path if P contains every vertex of G. Let G be a graph of order p (≥ 2) such that deg v ≥ (p − 1)/2 for every vertex v of G. Prove that G contains a hamiltonian path. (Hint: Construct a graph H from G by adding a new vertex w to G and joining w to each vertex of G. Show that H satisfies the hypothesis of Theorem 3.4, so that H is hamiltonian. Use this fact to prove that G has a hamiltonian path.)

23. True or false? Every eulerian graph is hamiltonian. Explain.

24. True or false? Every hamiltonian graph is eulerian. Explain.

*25. Suppose a group of university students are at a party. Represent this situation by a graph G, where the vertices of G correspond to the students at the party and two vertices of G are adjacent if and only if the corresponding man and woman have had a date together. If G is hamiltonian, prove that the number of men at the party equals the number of women at the party. (Hint: Label each vertex M or W according to whether the vertex corresponds to a man or a woman. Now use the fact that G possesses a hamiltonian cycle to establish the proof.)

26. Suppose we have a group of students (at least four) at a campus party, where the number of men at the party equals the number of women at the party. Suppose further that every man has had a date with every woman. Represent this situation by a graph G as in Exercise 25. Show that G is hamiltonian.

27. Determine whether the graph of Figure 3.21 is hamiltonian.

Figure 3.21

28. Referring to Example 3.2, show that in a 5-by-5 maze it is not possible to start at one of the squares, proceed to each square exactly once, and return to the starting square. (Hint: Color the squares alternately red and black.)

*29. Generalize Example 3.2 and Exercise 28 by finding exactly which pairs of positive integers m, n determine an m-by-n maze with the property that you may start at any square, proceed to each square exactly once, and return to the starting square.

30. Solve the Traveling Salesman Problem for the network shown in Figure 3.22.

Figure 3.22

*31. Consider the Traveling Salesman Problem for the network shown in Figure 3.23. Starting from each of the five cities, determine the cost of a hamiltonian cycle obtained by always proceeding to the next city using the cheapest possible route. Show that in no case will this produce a hamiltonian cycle of least cost.

Figure 3.23

Suggestions for Further Reading

The student might enjoy reading Newman’s [6] account of the Königsberg Bridge Problem, as well as Ball and Coxeter’s [1] treatment of Hamilton’s “Around the World” game. There are several expository articles written on hamiltonian graphs, including the rather elementary article [2]. An article dealing with eulerian graphs was written by Meyer [5]. You can find more information about the Traveling Salesman Problem by reading Flood [3]. Several variations of the transportation problems discussed in this chapter are mentioned in [4].

W. W. R. Ball and H.S. M. Coxeter, Mathematical Recreation and Essays. Macmillan, New York (1947).

G. Chartrand, S. F. Kapoor, and H. V. Kronk, “The many facets of hamiltonian graphs.” The Mathematics Student. 41 (1973), pp. 327–336.

M. Flood, “The travelling salesman problem.” Operations Research. 4 (1956), pp. 61–75.

L. Lesniak and G. Chartrand, “On traversing graphs.” Bulletin of the Iranian Mathematical Society. 1 (1974), pp. 1–17.

W. Meyer, “Garbage collecting, Sunday strolls, and soldering problems.” The Mathematics Teacher. 65 (1972), pp. 307–309.

J. Newman, “Leonhard Euler and the Königsberg Bridges.” Scientific American. 189 (1953), pp. 66–70.

Chapter 4

Connection Problems

Numerous real-life situations involve proceeding as inexpensively or as quickly as possible from one location to another, or from one state to another. We consider two problems of this type, one involving graphs and the other involving digraphs.

4.1 The Minimal Connector Problem : An Introduction to Trees

The Minimal Connector Problem

SUPPOSE WE HAVE a collection of n cities, and we wish to construct a railroad system connecting them. Assume that we know the cost of building tracks between every two cities. Due to the current economic situation, we must construct the system as cheaply as possible—regardless of how inconvenient it turns out for prospective passengers. The question is: how should this railroad system be built?

The desired railway system can be represented by a graph G whose vertices correspond to the cities involved and in which two vertices are adjacent if a track runs between the two corresponding cities. It is essential, of course, that G be connected. However, it is also necessary that G not contain any cycles; for if G has a cycle and e is an edge on that cycle, then by Theorem 2.5, e is not a bridge and G − e is connected. Hence, it would be possible to leave out a set of tracks between two cities and still have all cities connected, implying that the original railway system is not the cheapest. Thus, G must be connected but must contain no cycles.

Before solving the Minimal Connector Problem, we need to investigate in more detail the type of graph we have just encountered. Any connected graph that has no cycles is called a tree. As we already noted, every edge of a tree is a bridge. It is customary to define a graph without any cycles (be it connected or not) as a forest. Hence, each component of a forest is a tree. The word “tree” is used for these graphs because, when drawn, some of them may look like trees (see Figure 4.1).

Figure 4.1

We now present a few interesting properties of trees.

Theorem 4.1

Let u and v be two vertices of a tree G. Then there is exactly one u−v path in G.

Proof

We know that there is at least one u−v path in G since every tree is connected. We show that G cannot have more than one u−v path. Suppose there are two u−v paths in G, say P₁ and P₂. Since the paths P₁ and P₂ are different, there must be a vertex w₁ (possibly w₁ = u) on both paths such that the vertex following w₁ on P₁ is not the same as the vertex following w₁ on P₂. Since P₁ and P₂ terminate at the vertex v, there is a first vertex after w₁, call it w₂, which P₁ and P₂ have in common (possibly w₂ = v). However, that part of P₁ from w₁ to w₂ together with that part of P₂ from w₁ to w₂ form a cycle in G. This contradicts the fact that G has no cycles. Therefore, G has exactly one u−v path. ▋

The next result gives us a relationship between the number of vertices and the number of edges in any tree.

Theorem 4.2

If G is a tree of order p and size q, then q = p − 1.

Proof

The proof is by the second principle of mathematical induction (see Theorem A.8 of the Appendix.) Let Sn denote the statement: Every tree of order n has n − 1 edges. We prove that Sn is true for every positive integer n.

The statement S₁ is true since there is only one tree of order one and that tree has zero edges. Let k > 1 be a positive integer, and assume that the statements Si, 1 ≤ i < k, are true. To prove that the statement Sk is true, we consider a tree T of order k. Let e = uv be an edge of T. Since every edge of a tree is a bridge, the graph T–e is disconnected. In fact, T–e is a forest with two components, namely, a tree T₁ containing u, and a tree T₂ containing v. Suppose T₁ has order k₁ and T₂ has order k₂. We observe that 1 ≤ k₁ < k, 1 ≤ k₂ < k, and k₁ + k₂ = k. Since and are true statements, T₁ has k₁ − 1 edges and T₂ has k₂ − 1 edges. Therefore, T has size

(k₁ − 1) + (k₂ − 1) + 1 = k₁ + k₂ − 1 = k − 1.

Hence Sk is true, implying that Sn is true for every positive integer n. ▋

We now return to the Minimal Connector Problem. Suppose we have a connected undirected network G. (Thus, each edge of G has a value assigned to it.) We can construct a tree T such that T is a subgraph of G and T contains every vertex of G. Such a tree is called a spanning tree of G.

We wish to construct a particular spanning tree T of the connected undirected network G representing the possible railway systems of the Minimal Connector Problem. For the first edge e₁ of T, we select any edge of G of minimum value. As a second edge e₂ of T, we select any remaining edge of G having minimum value. For e₃ we choose any remaining edge of minimum value which does not form a cycle with the previously selected edges. We continue this procedure until we obtain a spanning tree T. A spanning tree arrived at in such a manner is called an economy tree.

It should be clear at this point that finding a solution to the Minimal Connector Problem is equivalent to determining, for a given connected undirected network G, a spanning tree T whose value (the sum of the values of its edges) is a minimum.

Theorem 4.3

Solution of the Minimal Connector Problem

Let G be a connected undirected network, and let T be an economy tree of G. Then T is a spanning tree whose value is a minimum.

Proof

For each edge e of G, let f(e) denote the value of e. Furthermore, if H is a subgraph of G, then we define f(H) to be ∑ f(e), where the sum is taken over all edges of H.

If the network G has order p, then an economy tree T of G has p − 1 edges. Let the edges of T be ordered e₁, e₂ , . . . , ep−1, as described earlier. The value ƒ(T) of T is then given by

Let T₀ be a spanning tree of G having minimum value. We show that f(T₀) ≥ ƒ(T the desired result.

If the trees T₀ and T are not identical, then T has one or more edges which are not in T₀. Using the ordering on the edges of T, we let ei, 1 ≤ i ≤ p − 1, be the first edge of T not in T₀. We add the edge ei to T₀, obtaining a graph G₀. Suppose ei = uv. Then a u−v path P exists in T₀, and so P together with ei produces a cycle C in G₀. Since T contains no cycles, there must be an edge e₀ in C which is not in T. The graph T′₀ = G₀ − e₀ is also a spanning tree of G, and

ƒ(T′₀) = ƒ(T₀) + ƒ(ei) − ƒ(e₀).

However, we know that ƒ(T₀) ≤ ƒ(T′₀), so

ƒ(T₀) − ƒ(T′₀) ≤ 0.

Since

ƒ(T₀) − ƒ(T′₀) = ƒ(e₀) − ƒ(e¡),

it follows that

ƒ(e₀) ≤ ƒ(ei).

However, by the manner in which T was constructed, ei is an edge of smallest value which can be added to the edges e₁, e₂ , . . . , ei−1 without producing a cycle. Also, if e₀ is added to the edges e₁, e₂, . . . , ei−1, no cycle is produced either. Therefore, ƒ(ei) = ƒ(e₀), so that ƒ(T′₀) = ƒ(T₀).

We have shown in this fashion the existence of a spanning tree of minimum value, namely T′₀, such that the number of edges common to T′₀ and T exceeds the number of edges common to T₀ and T by one edge, namely ei. By continuing this procedure, we finally arrive at a spanning tree with minimum value which is identical to T. Therefore, T has minimum value. ▇

Example 4.1

Suppose A, B, C, and D are four cities located at the corners of a square, one mile on a side. Assume that the cost of building a track between any two cities is proportional to the distance between them. Determine the least expensive railroad system connecting all four cities.

We can represent this situation by the undirected network G of Figure 4.2. The solution consists of determining an economy tree T of G. One such tree can be found by selecting the edges AB, BC, and CD.

Figure 4.2

We consider a couple of other situations involving trees.

Perhaps one of the most familiar uses of trees occurs in family trees. Figure 4.3 shows the known ancestral family tree of international playboy Rupert Rupert.

Figure 4.3

Figure 4.4

We also can describe sorting processes with the aid of trees. For example, in the small town of San Locos, incoming mail is sorted by hand. The mail is divided by districts and then more finely divided for delivery. Figure 4.4 shows one possible post office sorting plan.

Problem Set 4.1

1. How many different trees (pairwise non-isomorphic) are there of order:

two?

three?

four?

five?

six?

2. Determine the different (non-isomorphic) spanning trees of the graph G in Figure 4.5.

Figure 4.5

3. Is it possible for a tree to be a regular graph? Explain.

4. Let G be a graph possessing the property that for every two distinct vertices u and v of G, there exists exactly one u−v path. Prove that G is a tree.

5. By Theorem 4.1 and Exercise 4, it follows that trees are characterized by the fact that for every two distinct vertices u and v in a tree T, T contains exactly one u−v path (that is, trees are the only graphs with this property). Give an example of a graph having the property that for every two distinct vertices u and v, there exist exactly two u−v paths.

6. If a graph G of order p has size q = p − 1, must G be a tree? Explain.

*7. Let G be a forest of order p and size q having k components. Obtain an expression for q in terms of p and k.

*8. Prove that if G is a connected graph of order p and size q, then q ≥ p − 1.

*9. If G is a connected graph of order p and size q such that q = p − 1, prove that G is a tree.

*10. Let G be a graph of order p and size q such that q ≥ p ≥ 3. Show that G must contain at least one cycle.

*11. Let G be a graph of order p and size q such that q = p − 1. Prove that if G is a forest, then G is a tree. (Hint: Try an indirect proof.)

12. Determine a spanning tree of minimum value in the undirected network G of Figure 4.6.

13. The following problems involve Example 4.1.

Show that there are four possible economy trees in G. What factors might you consider in deciding which economy tree to select?

A city E lies in the middle of the square determined by A, B, C, and D. The state chamber of commerce decides that all five cities should be connected by a railroad system. What is the least expensive system which can be constructed if:

(i) the system involving A, B, C, and D has already been constructed?

(ii) the system involving A, B, C, and D has not yet been constructed?

Figure 4.6

Might there be four cities situated approximately as A, B, C, and D where the cost of constructing track between any two cities is not proportional to the distance between them? Explain how this might happen.

14. Agents A, B, C, D, E, F, G, and H are political conspirators in what has become known as the “Blottergate Affair.” In order to coordinate their cover-up efforts, it is vital that each agent be able to communicate directly or indirectly with every other conspirator. Such communications involve a certain amount of risk to everyone. Below is a table of “risk factors” associated with direct communication between the indicated parties. All other direct communications are too likely to expose the cover-up scheme. What is the least total risk involved in a connecting system?

15. Draw as much of your family tree as you are familiar with.

*16. Given a tree T, what properties must T possess in order for it to be a family tree?

*17. Figure 4.7 presents a diagram of a prison for political dissidents. The prisoners have been divided into seven groups as shown. A spy plans to help all the prisoners escape by blowing up the gates in the prison walls. Due to the danger of this plan, he wants to destroy as few gates as possible and still allow all prisoners to escape. How many gates must be blasted to do this? Can a more general problem be solved? How is this related to trees?

Figure 4.7

18. Trees can also be useful in categorizing the possible outcomes of certain events. For example, suppose football teams from Oakland and Kansas City play twice during the regular season. Assuming that a tie is unlikely, we give in Figure 4.8 the possible outcomes of the two games. Observe that there are two ways for Oakland (O) and Kansas City (K) to each win one of two games played, namely, the orders OK and KO. This equals exactly the 2! = 2 permutations of the set {O, K}. With this example in mind, use a tree to aid you in listing all 24 permutations of the set V = {v₁, v₂, v₃, v₄}.

Figure 4.8

*4.2 Trees and Probability

We have just seen (in Exercise 18) how we can use trees in counting or listing possible outcomes of situations. Trees can also be helpful, in certain cases, in calculating probabilities. We illustrate this idea briefly in this section.

Probability theory is a vast and deep area of mathematics; however, we shall consider only a few elementary examples from this subject. Numerous books have been written on probability, and every finite mathematics book deals with this topic to some extent.

We shall not present a formal definition of probability. Intuitively, we say that probability deals with what are called “experiments” of various types and with possible outcomes, called “events,” of the experiments. We consider a few examples to give the reader a taste of the subject.

Example 4.2

A container (often referred to as an “urn” by people who work in probability theory) contains five balls of equal size, two colored red and three colored blue. A ball is selected at random from the container.

What is the probability that the ball is red?

What is the probability that the ball is blue?

What is the probability that the ball is red or blue?

What is the probability that the ball is green?

In this example the experiment consists of selecting a ball. There are five possible outcomes and each outcome is equally likely to occur. Therefore, we say that (a) the probability of selecting a red ball is 2/5 = 0.4, and (b) the probability of selecting a blue ball is 3/5 = 0.6. Since every ball is red or blue, (c) the probability of selecting a red or blue ball is 5/5 = 1. Since no ball is green, (d) the probability of selecting a green ball is 0/5 = 0.

Example 4.3

A card is drawn at random from a shuffled, standard deck of 52 playing cards. What is the probability that the card is a jack?

Of the 52 cards, 4 are jacks; thus, the probability of drawing a jack is 4/52 = 1/13.

Example 4.4

A fair coin is flipped. (A “fair” coin means that heads or tails are equally likely to appear if the coin is flipped.) What is the probability that heads comes up?

There are two possibilities: heads or tails. Since each outcome is equally likely, the probability of heads coming up is 1/2 = 0.5.

Example 4.5

This is a continuation of the preceding example. A fair coin is flipped twice.

What is the probability that heads comes up both times?

What is the probability that tails comes up both times?

What is the probability that heads and tails occur once each?

There is more than one way of answering these questions; however, we consider only one technique. The probability that heads occurs on the first flip is 0.5, as we saw in Example 4.4. The probability that heads occurs on the second flip does not depend on what happened on the first flip, so this probability is also 0.5. This “independence” implies that we obtain the answer to (a) by multiplying 0.5 and 0.5; that is, the probability that heads comes up both times is (0.5)(0.5) = 0.25. By the same kind of argument, the probability (b) that tails occurs both times is (0.5)(0.5) = 0.25. There are two ways that heads and tails can occur once each; namely, heads could occur on the first flip and tails on the second, or tails could occur on the first flip and heads on the second. This probability (c) is (0.5)(0.5) + (0.5)(0.5) = 0.5. The possibilities for the two flips and the corresponding probabilities can be given by means of a tree, as shown in Figure 4.9.

Figure 4.9

Reading from left to right, we see the four possibilities for the two flips of a coin: HH (heads followed by heads), HT, TH, and TT. The probability of each event is then obtained by multiplying the probabilities associated with the edges on the corresponding paths.

Example 4.6

We are faced with three containers, numbered 1, 2, and 3. Container 1 contains one black ball and two white balls. Container 2 has one black ball and three white balls, while Container 3 holds only one ball, colored black. Therefore, the three containers have a total of three black balls and five white balls. We select a container at random and then select a ball at random from the chosen container. Is it more likely that a black ball or a white ball is chosen?

Figure 4.10

The situation is described by the tree of Figure 4.10. Since each container is equally likely to be selected, the probability that any particular one is chosen is 1/3. We calculate the probability that a white ball is selected. With the aid of the tree of Figure 4.10, we see that this probability is

Since this probability is less than 0.5, we conclude that we are more likely to choose a black ball.

Problem Set 4.2

19. A die (a cube whose six faces show the numbers 1 through 6) is tossed.

What is the probability that 6 is thrown?

What is the probability that 1 is thrown?

20. A die is tossed and then tossed again.

What is the probability that 6 occurs both times?

What is the probability that the sum of the numbers on the two throws is 8? [Hint: List the various ways in which 8 can be obtained.]

21. A fair coin is flipped four times.

Draw a tree showing the possible outcomes.

Determine the probability that heads and tails occur twice each.

22. Two urns, labeled A and B, contain red and green balls of equal size. Urn A contains one red and two green balls; urn B holds three red and two green balls. An urn is selected at random and then a ball is selected at random from the chosen urn. Use a tree to determine which colored ball is more likely to be selected.

23. Two teams A and B have played several basketball games, with A winning two-thirds of the games. These teams are now involved in a play-off where the winner is the first team to win two games. Assuming the probability of A winning a game is 2/3, use a tree to determine the probability of A winning the play-off.

4.3 PERT and the Critical Path Method

The management sciences abound with situations requiring planning and scheduling. Many of the problems encountered are extremely complicated, and careful analysis of these problems commonly requires a sound background in a variety of mathematical subjects. However, with our background in graph theory, it is possible to acquire a feel for handling such problems.

In Section 4.1 we discussed paths and connection in graphs; in this section, we discuss paths and connection in digraphs (see Section 1.5). For vertices u and v of a digraph D, a u−v path in D is an alternating sequence of distinct vertices and arcs of D, beginning with u and ending with v, such that each arc is incident from the vertex immediately preceding it and incident to the vertex immediately following it. For example, in the digraph D of Figure 4.11, the sequence v₁, e₁, v₃, e₃, v₄, e₅, v₅ is a v₁−v₅ path. This path could be denoted more simply by v₁, v₃, v₄, v₅. Note that v₁, v₃, v₅ is not a path because of the direction of e₄. Similarly, v₁, v₃, v₄, v₆, v₅ is not a v₁−v₅ path.

Figure 4.11

Suppose we have a project to complete. If the project is sufficiently complex, it is useful, if not essential, to thoroughly analyze it before making any attempt to begin work on the project. A common procedure is to divide the project into a number of smaller subprojects, which we call activities; that is, a project is composed of activities. Ordinarily, these activities are interrelated, and a certain activity may not be initiated until other activities have been completed. Let us consider a simple illustration before proceeding further.

Example 4.7

Suppose you have a rather spacious area in the basement of your home, and you would like to convert this space into a recreation room. You decide that you will panel the walls, install a ceiling, have the floor carpeted, and assemble a pool table. You may be rather handy at performing such “activities,” but for the sake of the example, let us assume that you will have all these things done professionally. The activities, together with their estimated completion times, are:

| Activity | Time (hours)
P | Assemble pool table | 4
F | Carpet the floor | 6
W | Panel the walls | 6
C | Install ceiling | 8

It would be considerably simpler to assemble the pool table after the floor has been carpeted; hence we decide that F should precede P. With the exception of this restriction, any activities may be performed at the same time (although there is a possibility that the workers will get in each other’s way). We can represent this situation by the “activity digraph” D of Figure 4.12. Each of the four activities is represented by a vertex, marked with the length of time necessary to complete the activity. We introduce two other vertices, labeled S and E, to indicate the start and end of the project. A time of zero is assigned to each of these “activities.”

Although it is easy to see that the entire project could be completed in 4 + 6 + 6 + 8 = 24 hours, it is not difficult to see that it could also be done in 10 hours. Specifically, after the carpeting is laid, the pool table could be assembled. These two activities take 10 hours, and while these two activities are in progress, the walls could be paneled and the ceiling could be installed.

Figure 4.12

We now give a more formal definition of an activity digraph. Given a project composed of activities, we define a digraph D containing a vertex labeled S and a vertex labeled E, and such that the remaining vertices of D correspond to, and are labeled the same as, the activities. The vertex S is directed to a vertex v if the activity v may start without any other activity first being completed, and vertex w is directed to vertex E if no activity requires that w be completed before that activity begins. Furthermore, vertex x of D is directed to vertex y if and only if no activity need intervene between the completion of x and the beginning of y. Finally, we associate the number 0 with the vertices S and E, and we associate the number t with the vertex w if activity w requires t units of time for completion. The digraph D is called the activity digraph of the project.

Techniques referred to as PERT (Program Evaluation and Review Technique) and the critical path method make use of activity digraphs. A longest path (in units of time) in an activity digraph D is called a critical path of D. The activity digraph of Figure 4.12 has exactly one critical path, namely, S, F, P, E, and its time-length is 10 hours. It is no coincidence that the length of the critical path in this digraph equals the minimum time necessary to complete the project, as we now show.

Theorem 4.4

Let D be the activity digraph associated with a given project. Then the time-length of a critical path in D equals the minimum time necessary to complete the project.

Proof

Let

P:S = v₀, v₁, . . . , vn = E

be a critical path in D. Suppose the time-length of P is t. Since the activity vi, 0 < i ≤ n, cannot begin until the activity vi−1 is completed, the time required to complete the entire project cannot be less than t; otherwise, not all of the activities of P could be completed.

It only remains for us to show that each activity of D may be performed during the t units of time needed to complete the activities of P. Let A be an arbitrary activity of the project. If A is an activity of P, then clearly A can be performed. Hence we assume A is not an activity of P.

Let Q be an S-E path of maximum time-length containing A. Then Q must begin at start S and must terminate at end E. Hence the paths P and Q have at least two vertices in common, namely S and E. Therefore, there exists a subpath Q′: w₀, w₁,..., wk of Q such that A belongs to Q′, w₀ = vi and wk = vj for 0 ≤ i < j ≤ n, and none of the vertices w₁, w₂,... wk−1 belong to P. Since P is a critical path, the time-length of the path

S = v₀, v₁,..., vi = w₀, w₁, w₂,..., wk = vj, vj + 1,...., vn = E

is at most t. This implies that the activities w₁, w₂, . . . ., wk−1 (including A) of Q may be performed while the activities vi+1, vi+2, . . . , vj−1 of P are taking place. Since A was arbitrary, every activity of the project may be completed in t units of time. ▇

Example 4.8

A common example of the critical path method occurs in planning the construction of something rather complicated, such as a house. Let us assume that building a house can be described by the following activities:

| Activity | Time (days)
C | Clear land | 1
F | Build foundation | 3
U | Build upper structure | 15
E₁ | Electrical work | 9
P | Plumbing work | 5
E₂ | Complete exterior work | 12
I | Complete interior work | 10
L | Landscaping | 6

A possible activity digraph is indicated in Figure 4.13.

Figure 4.13

There is only one critical path in this case, namely S, C, F, U, E₁, I, E, and its time-length is 38 days. Thus, theoretically the house could be completed in 38 days.

As we mentioned at the beginning of this section, the discussion given here is meant only to present a flavor of the problems. In reality, this is a gross oversimplification. For example, if we say activity A₀ will take t₀ units of time, how do we really know this? Actually, t₀ may be only the average time it takes to perform activities similar to A₀. It is highly unlikely that the completion of A₀ will take exactly t₀ units, even after rounding off in some manner. In a particular case it might be valuable to know the minimum amount of time it ordinarily takes to complete A₀, as well as the maximum amount of time. If activity A₁ is to begin once A₀ is completed, we may wish to have our workers present and ready to begin A₁ just as A₀ concludes. However, in all probability this must be set up according to some prearranged schedule. It is quite possible that when the workers for A₁ arrive, either A₀ has not yet been completed, or A₀ was completed earlier and time has been wasted. In either case, it is likely that money also has been wasted.

Problem Set 4.3

24. Which of the following paths exist in the digraph D of Figure 4.11 ? If one exists, determine such a path.

v₇−v₆ path

v₁−v₇ path

v₁−v₆ path

v₄−v₂ path

v₇−v₁ path

25. Assign “times” to the vertices of the activity digraph D of Figure 4.14 and use them to determine a critical path in D.

Figure 4.14

26. Explain why the digraph of Figure 4.15 cannot be an activity digraph.

Figure 4.15

27. Explain why the digraph of Figure 4.16 cannot be an activity digraph.

Figure 4.16

28. Suppose we wish to construct a widget. The usual way of doing this is to divide this project into the following activities:

| Activities | Time (minutes)
F₁ | Construct foundation | 5
F₂ | Attach five flanges | 4
A₁ | Add antenna | 8
B₁ | Secure bolt in place | 15
A₂ | Slide in axles | 3
W | Affix all three wheels | 2
B₂ | Remove bolt | 1
C | Insert clamps | 4
P | Two coats of paint | 2

Assume the activity digraph is given in Figure 4.17. Determine all critical paths and their time-lengths.

Figure 4.17

29. Four women sharing an apartment have cooked dinner for a few of their friends and are planning the preparation of the dinner table. Estimate the time required (in minutes) to complete each of the following activities, draw a possible activity digraph, and determine the minimum time needed to complete the project.

Activities

C | Put tablecloth on table
N | Fold napkins and place on table
D | Place dishes and silverware on table
W₁ | Put water and ice in water glasses
W₂ | Pour wine into wine glasses
F | Place plates of food on table

30. Think of a project of your own and analyze it by means of an activity digraph.

31. Referring to Example 4.8, suppose you are the contractor. The workers who are to build the foundation say it will take them from 2 to 4 days to complete the job. What are the advantages and disadvantages of having the workers who are to build the upper structure report on the job 2, 3, or 4 days after the foundation is started?

*32. Characterize those digraphs which are activity digraphs, i.e., determine a necessary and sufficient condition for a digraph to be an activity digraph, and give a proof of this result.

Suggestions for Further Reading

For other versions of “The Minimal Connector Problem,” the reader should refer to Ore [6] and Wilson [7]. Articles pertaining to trees and their properties include those by Anderson and Harary [1] and Harary and Manvel [3]. Much has been written on probability and trees; one interesting and readable paper is by Zimmerman [8].

A good discussion of the critical path method is given in Malkevitch and Meyer [4]. More advanced treatments of this subject may be found in Busacker and Saaty [2] and in Marshall [5].

S. S. Anderson and F. Harary, “Trees and unicyclic graphs.” The Mathematics Teacher, 60 (1967), pp. 345–348.

R. G. Busacker and T. L. Saaty, Finite Graphs and Networks. McGraw-Hill, New York (1965).

F. Harary and B. Manvel, “Trees.” Scripta Mathematica, 28 (1970), pp. 327–333.

J. Malkevitch and W. Meyer, Graphs, Models, and Finite Mathematics. Prentice-Hall, Englewood Cliffs, N.J. (1974).

C. W. Marshall, Applied Graph Theory. Wiley-Interscience, New York (1971).

O. Ore, Graphs and Their Uses. Random House, New York (1963).

R. J. Wilson, Introduction to Graph Theory. Academic Press, New York (1972).

M. Zimmerman, “Matrix multiplication as an application of the principle of combinatorial analysis.” Pi Mu Epsilon Journal, 6 (1975), pp. 166–175.

Chapter 5

Party Problems

Numerous situations with graph theory overtones are expressible in terms of gatherings of people. For the purpose of adding a little spice to the problems, we may further assume, without loss of generality, that these people are attending a party. For example, suppose several people are at a party, and certain of these people are friends of one another. Is it possible to seat everyone around a large circular table so that each guest is sitting next to two of his or her friends?

Of course, it is impossible to answer the question with only the information given. However, the situation can be modeled by a graph G whose vertices represent the people and where two vertices are adjacent if and only if the corresponding individuals are friends of each other. Then the stated question has an affirmative answer if and only if G is hamiltonian. In this chapter we consider some other problems described in terms of parties.

5.1 The Problem of the Eccentric Hosts: An Introduction to Ramsey Numbers

A man and his wife are planning a dinner party, but they each have certain peculiarities. The man likes to have everyone at the dinner table know one another, for he feels this creates more harmony during the meal. On the other hand, his wife thinks that no two people at the dinner table should know each other, for she believes one important aspect of dinner parties is the opportunity it gives people for making new acquaintances. Despite this difference of opinion between husband and wife, they are a happily married couple, and both will be happy if either’s wishes are fulfilled. Hence, several tables are set, two of which are designated A and B. At table A, the man’s table, all guests are to know one another; while at table B, the wife’s table, no two guests are to know each other. We may now state our problem.

The Problem of the Eccentric Hosts

SUPPOSE TABLE A is to seat m people and table B is to seat n people. All guests at table A are to know one another, while no two people seated at table B are to know each other. What is the least number of people that may attend a dinner party so that at least one of the two tables can be filled according to these rules?

For each collection of p people present at the party, we can represent their situation by a graph G of order p whose vertices correspond to the people, and such that two vertices of G are adjacent if and only if the corresponding people know each other. In order to state the Problem of the Eccentric Hosts in mathematical terms, however, a few additional definitions are convenient.

The complement Ḡ of a graph G is a graph having the same vertex set as G, but with the property that two vertices of Ḡ are adjacent if and only if the same two vertices of G are not adjacent. Figure 5.1 shows a graph G and its complement Ḡ.

Figure 5.1

Let F₁ and F₂ be any two graphs. We define the Ramsey number r(F₁, F₂) to be the least integer p such that for every graph G of order p, either G contains F₁ as a subgraph or Ḡ contains F₂ as a subgraph. These numbers are named after Frank Ramsey, who proved that for every two complete graphs Km and Kn, the Ramsey number r(Km, Kn) exists. This, in turn, implies that r(F₁, F₂) exists for every two graphs F₁ and F₂.

The following result is rather elementary, yet important.

Theorem 5.1

For every two graphs F₁ and F₂,

r(F₁, F₂) = r(F₂, F₁).

Proof

Let r(F₁, F₂) = p and r(F₂, F₁) = p₀. We show that p = p₀. Let H be any graph of order p, and consider , also of order p. Since r(F₁, F₂) = p, either contains F₁ as a subgraph or = H contains F₂ as a subgraph. Hence, for every graph H of order p, either H contains F₂ as a subgraph or contains F₁ as a subgraph. Because r(F₂, F₁) = p₀, the number p cannot be smaller than p₀, so p ≥ p₀.

Now suppose G is an arbitrary graph of order p₀. The graph Ḡ, also of order p₀, either contains F₂ as a subgraph or = G contains F₁ as a subgraph. Since r(F₁, F₂) = p, however, it follows that p₀ ≥ p, which, together with the preceding inequality, implies that P = P₀. ▋

The Problem of the Eccentric Hosts is equivalent to determining the Ramsey numbers r(Km, Kn). Unfortunately, for m ≥ 3 and n ≥ 3, very few Ramsey numbers have been found; hence, the Problem of the Eccentric Hosts is, in general, unsolved.

It is often convenient to investigate Ramsey numbers in another way. Consider a graph G of order p and its complement Ḡ. The edge sets E(G) and E(Ḡ) partition the edge set of Kp; that is, every edge of Kp belongs either to G or to Ḡ. If we take an edge of Kp belonging to G and color it red, and take an edge belonging to Ḡ and color it blue, then we may give an equivalent definition of Ramsey numbers. For graphs F₁ and F₂, the Ramsey number r(F₁, F₂) is defined as the least integer p such that if every edge of Kp is colored red or blue (in any manner whatsoever), then there exists either a red F₁ (a subgraph F₁ with all edges colored red) or a blue F₂.

It follows from the definition(s) that if either F₁ or F₂ has order 1, then r(F₁, F₂) = 1. As further illustrations, we evaluate r(K₃, K₂) and r(K₃, K₃).

Theorem 5.2

r(K₃, K₂) = 3.

Proof

First we observe that r(K₃, K₂) > 2, since if the one edge of K₂ is colored red, then K₂ contains neither a red K₃ nor a blue K₂. This shows it is not true that for every graph of order two whose edge is colored red or blue, there exists either a red K₃ or a blue K₂.

We can verify, however, that if the edges of K₃ are colored red or blue, then there exists a red K₃ or a blue K₂. If all edges are colored red, we have a red K₃; if not, at least one edge is colored blue, producing a blue K₂. Therefore, r(K₃, K₂) = 3. ▋

One of the best known Ramsey numbers is r(K₃, K₃).

Theorem 5.3

r(K₃, K₃) = 6.

Proof

First we observe that r(K₃, K₃) > 5 by noting that neither the graph H of Figure 5.2 nor its complement contains K₃ as a subgraph.

Figure 5.2

In order to show that r(K₃, K₃) = 6, it suffices to prove that if the edges of K₆ are colored red or blue, there is a red K₃ or a blue K₃. Consider some vertex of K₆, say v₁. Since v₁ is incident with five edges, at least three of the five edges must be colored the same, say red. (The argument is essentially the same if the majority of the edges incident with v₁ are colored blue.) Suppose v₁ v₂, v₁ v₃, and v₁ v₄ are red edges. If any of the edges v₂ v₃, v₂ v₄, and v₃ v₄ are red, we have a red K₃ ; if not, these three edges form a blue K₃. Hence, r(K₃, K₃) = 6. ▋

From Theorem 5.3, it follows that the eccentric hosts must have at least six people present at their dinner party in order to be absolutely certain that either three mutual acquaintances may be seated at the husband’s table or three mutual strangers may be seated at the wife’s table.

Problem Set 5.1

1. Figure 5.2 shows a cycle of order 5 and its complement. Draw a cycle of order 4 and its complement. Do the same for a cycle of order 6.

2. Let G be a graph of order p and size q. Determine the order and size of Ḡ.

3. Let G be a graph whose vertices have degrees d₁, d₂, . . . , d₁₀. Determine the degrees of the vertices of Ḡ.

*4. Let G be a disconnected graph. Prove that Ḡ is connected.

5. Give an example of a connected graph whose complement also is connected.

*6. Let G be a regular graph of even order p ≥ 4. Prove that at least one of G and Ḡ is hamiltonian.

7. A graph G is self-complementary if G and Ḡ are isomorphic. Figure 5.2 shows that a cycle of order 5 is self-complementary. Also, K₁ is self-complementary.

Give an example of a self-complementary graph of order 4.

Show that there are no self-complementary graphs of order 2 or 3.

*8. See the definition of “self-complementary” in Exercise 7.

Show that if a graph G has order p, and p is of the form p = 4n + 2 (i.e., p = 2, 6, 10, ...) or p is of the form p = 4n + 3 (i.e., p = 3, 7, 11, ...), then G is not self-complementary.

Use part (a) as a hint to find a necessary condition for a graph G of order p to be self-complementary.

Find a necessary and sufficient condition for a positive integer p to be the order of some self-complementary graph.

9. As we mentioned, Ramsey proved that for every two complete graphs Km and Kn, r(Km, Kn) exists. What exactly does this mean?

10. Let F₁ be a graph of order m and F₂ be a graph of order n. Explain why r(F₁, F₂) ≤ r(Km, Kn).

11. Suppose that the edges of K₇ are colored red and blue. Why does it follow that K₇ must contain a red K₃ or a blue K₃?

*12. Let G be a graph of order r(Km, Kn) − 1, where m, n ≥ 2. Prove that either G contains Km−1 as a subgraph or Ḡ contains Kn−1 as a subgraph.

*13. Let Pn denote a path with n vertices (and n − 1 edges).

Determine r(P₃, P₃).

Determine r(P₃, K₃).

*14.

Generalize the concept of Ramsey numbers to define r(F₁, F₂, F₃) and, more generally, r(F₁ F₂, ..., Fn). [Hint: Consider the second definition discussed for r(F₁, F₂).]

Show that r(K₂, K₂, K₂) = 2.

Determine r(K₂, K₂, K₃).

Determine r(K₂, K₃, K₃).

15. Suppose we have a group of people attending a party, and every two people are either acquaintances or strangers to each other. How many people must be present at the party to guarantee the presence of either three mutual acquaintances or three mutual strangers? Explain.

*16. Suppose we have a group of people attending a party, and every two people are either acquainted or unknown to each other. How many people must be present at the party for some person to be an acquaintance of at least three people or for some person to be a stranger to at least three people?

5.2 The Dancing Problem: An Introduction to Matching

Once again we are planning a party. This time it is to be quite an affair, and no expense is being spared. Indeed, even a band (Cicero Fudge and His Sweet Notes) has been hired, and there will be dancing. During each musical number, we would like as many guests dancing (with a partner) as possible. Of course, if we wish to have all guests dancing at one time, then we must invite an equal number of men and women; however, this may be neither possible nor desirable. Let us assume that there are at least as many men at the party as there are women. Then we would like every woman dancing with a male partner during each musical selection. This may not be easy to accomplish, however, for it may happen that each woman will only dance with certain of the men, and vice versa. For example, a man may very well be willing to dance with his wife, but this idea might be totally repugnant to his wife. Hence our goal is not only to have as many guests dancing as possible, but also to match all dancers with compatible partners. We now state our problem.

The Dancing Problem

SUPPOSE WE HAVE A GROUP of men and women at a party, with at least as many men present as there are women. Under what conditions is it possible to have all women dance with equally many men so that each dancing couple is compatible?

As before, we explore this problem by setting up a mathematical model using graphs. Let G be a graph whose vertex set represents the people at the party, and such that two vertices are adjacent if and only if the corresponding people are compatible dancing partners. It is possible for all women to be dancing at the same time if and only if G contains a 1-regular subgraph F such that the number of edges in F equals the number of women.

A few new graphical definitions will make this problem easier to discuss. A graph G is called bipartite if it is possible to partition the vertex set of G into two subsets, say V₁ and V₂, so that every edge of G joins a vertex of V₁ with a vertex of V₂, and no vertex joins another vertex of its own set. In Figure 5.3 we have redrawn a graph G to illustrate its bipartite property. Thus, for this graph, we could let V₁ = {v₁, v₃, v₅, v₇} and V₂ = {v₂, v4, v₆, v₈, v₉}.

Figure 5.3

Let G be a bipartite graph whose vertex set is partitioned into subsets V₁ and V₂, as just described. Let U₁ be a subset of V₁. We say that U₁ is matched to a subset U₂ of V₂ if G contains a 1-regular subgraph F whose vertex set is U₁ ∪ U₂. If U₁ is matched to U₂, then we must have ∣U₁∣ = ∣U₂∣. The subgraph F is referred to as a matching, for it matches (or pairs off) one set of vertices, namely U₁, with another set of vertices, namely U₂.

We illustrate this concept with the bipartite graph G of Figure 5.4. Here we let V₁ = {v₁, v₂, v₃, v₄}, V₂ = {w₁ w₂, w₃, w₄, w₅}, and U₁ = {v₁, v₃, v₄}. If we let U₂ = {w₁, w₂, w₅}, then we see that G contains the 1-regular subgraph F with vertex set U₁ ∪ U₂. Hence, U₁ is matched to U₂. Note that V₁ itself can be matched to a subset of V₂.

Figure 5.4

Again, let us assume G to be a bipartite graph with its vertex set partitioned into V₁ and V₂. If W₁ ⊆ V₁, then we denote by those vertices of V₂ adjacent with at least one vertex in W₁.The deficiency def (W₁) of W₁ in G is defined by

The set U₁ ⊆ V₁ is said to be nondeficient in G if no (nonempty) subset of U₁ has positive deficiency. We note that positive deficiency for a subset W₁ of U₁ means that there are more vertices in W₁ than there are vertices adjacent to the elements in W₁; hence, it would be hopeless to attempt matching W₁, to a subset of V₂.

Every subset of V₁ in the graph G of Figure 5.4 has negative or zero deficiency; that is, no subset of V₁ has positive deficiency. Hence,

(1) V₁ is nondeficient.

We have already observed that

(2) V₁ is matched to a subset of V₂.

We shall soon see that observations (1) and (2) are synonymous.

Returning to the Dancing Problem, we can now see that we have represented the situation by a bipartite graph G. If we denote by V₁ the vertices corresponding to the women, and by V₂ those vertices corresponding to the men, then we are asking conditions under which V₁ can be matched to a subset of V₂. We now give such conditions.

Theorem 5.4

Let G be a bipartite graph whose vertex set is partitioned into sets V₁ and V₂ so that every edge of G joins a vertex of V₁ with a vertex of V₂. Then V₁ can be matched to a subset of V₂ if and only if V₁ is nondeficient.

The proof of Theorem 5.4 is relatively complicated, and we omit it. It may be found in reference [1], however.

Applying Theorem 5.4 to the Dancing Problem, we can determine whether compatible dancing partners exist for all the women by computing the total number of compatible dancing partners for each subset of women. If the number of compatible dancing partners for each such subset is at least as large as the number of women in the subset, then compatible dancing partners can be found for all women for a single dance.

Example 5.1

Horace Barney is having a few friends over for drinks, namely Al, Bob, Chuck, Dave, Ed, and Frank. Horace has prepared some drinks prior to their arrival, but only one drink of a kind. The drinks are a daiquiri (d), a grasshopper (g), a Mai Tai (m), a Singapore sling (s), a Tom Collins (t), a whiskey sour (w), and a Barney special (b). Horace asks his friends which of these drinks they like, and their answers are: Al (g, s); Bob (g, t, w); Chuck (s, t, w); Dave (d, g, m, s); Ed (g, s, t, w); Frank (g, s, t). Is it possible for all of Horace’s friends to have a drink they like?

This situation is represented by the graph of Figure 5.5, where the vertices corresponding to Horace’s friends (the set V₂) are denoted by the first letters of their names. The problem is whether we can match V₂ to a subset of V₁. By Theorem 5.4, this is possible if and only if V₂ is nondeficient.

Figure 5.5

Let U₂ = {A, B, C, E, F}. Then = {g, s, t, w} and

so U₂ has positive deficiency. Hence, V₂ fails to be nondeficient, which implies that not all of Horace’s friends will have drinks they like.

Problem Set 5.2

17. Draw all the (non-isomorphic) bipartite graphs of order 4.

18. Show that the maximum size of a bipartite graph of order 10 is 25.

*19. Determine the maximum size of a bipartite graph of order p (≥2).

*20. Prove that every tree is a bipartite graph.

*21. Let G be a connected bipartite graph whose vertex set is partitioned into subsets V₁ and V₂ such that every edge of G joins a vertex of V₁ with a vertex of V₂. If G is regular, show that ∣V₁∣ = ∣V₂∣.

22. Let G be a bipartite graph whose vertex set is partitioned into subsets V₁ and V₂ such that every edge of G joins a vertex of V₁ with a vertex of V₂. If V₁ can be matched to a subset of V₂ and U₁ ⊆ V₁, U₁ ≠ ∅, can U₁ be matched to a subset of V₂?

*23. Let G be a bipartite graph whose vertex set is partitioned into subsets V₁ and V₂ such that every edge of G joins a vertex of V₁ with a vertex of V₂. Suppose V₁ can be matched to a subset of V₂. How can this property be described in terms of functions?

24. There are five women at a party [Alice (A), Barb (B), Connie (C), Debbie (D), and Edith (E)] with six men [Albert (a), Ben (b), Charles (c), David (d), Ed (e), and Frank (f)]. The compatible dancing partnerships are displayed by means of a graph in Figure 5.6. Is it possible to have all women dancing so that each dancing partnership is a compatible one?

Figure 5.6

25. The following problem is sometimes referred to as The Marriage Problem: Suppose we have a group of men and an equal number of women, and each man is acquainted with a certain number of the women. Under what conditions is it possible for all these men and women to get married, if each marriage is to take place between a couple already acquainted with each other?

26. How many different committees of four members can be formed from a group of five people? Is it possible to have a different chairperson for each committee?

27. A high school has openings for six teachers, with one teacher needed for each of these areas: mathematics, chemistry, physics, biology, psychology, and ecology. In order for a teacher to be hired in any particular area, he or she must have either majored or minored in that subject. The school receives six applications for these positions, namely: Mr. Arrowsmith (major: physics; minor: chemistry), Mr. Beckman (major: biology; minors: physics, psychology, ecology), Miss Chase (major: chemistry; minors: mathematics, physics), Mrs. Deerfield (majors: chemistry, biology; minors: psychology, ecology), Mr. Evans (major: chemistry; minor: mathematics), Ms. Form (major: mathematics; minor: physics). What is the largest number of applicants the school can hire?

Suggestions for Further Reading

In recent years the study of Ramsey numbers has developed into a theory, namely Ramsey Theory. Articles by Burr [2] and Harary [3] and a chapter in the book by Behzad, Chartrand and Lesniak-Foster [1] show the types of problems which have been investigated.

As indicated earlier, the subject of matchings is not a particularly easy one. More information on the subject can be obtained by reading Ore [4] and Wilson [5].

M. Behzad, G. Chartrand, and L. Lesniak-Foster, Graphs & Digraphs. Wadsworth International Group, Belmont, CA (1979).

S.A. Burr, “Generalized Ramsey theory for graphs—a survey,” Graphs and Combinatorics (R. A. Bari and F. Harary, eds.). Springer-Verlag, Berlin (1974), pp. 52–75.

F. Harary, “Recent results on generalized Ramsey theory for graphs,” Graph Theory and Applications (Y. Alavi, D. R. Lick, and A. T. White, eds.). Springer-Verlag (1972), pp. 125–138.

O. Ore, Graphs and Their Uses. Random House, New York (1963).

R. J. Wilson, Introduction to Graph Theory. Academic Press, New York (1972).

Chapter 6

Games and Puzzles

Thus far, the problems we have encountered have been serious problems, for the most part, and several have potentially important implications. However, part of the entertaining aspect of graph theory lies in its usefulness for analyzing certain kinds of games and puzzles. In this chapter we look into a few of the less serious applications of graphs.

6.1 The Problem of the Four Multicolored Cubes: A Solution to “Instant Insanity”

The “Instant Insanity” Problem

THE PUZZLE “INSTANT INSANITY” (which is a trade name used by the Parker Brothers Game Company) consists of four cubes, and each cube’s six faces are colored from four given colors: red, white, green, and blue. The object of the puzzle is to stack these cubes on top of one another in the form of a 1 x 1 x 4 rectangular prism so that each of the four colors appears on each of the prism’s four sides.

It is convenient first to describe how we will represent a cube. Each face f has an “opposite” face f′. Hence, the cube in Figure 6.1(a) may be represented as in Figure 6.1(b). Thus, in the cube of Figure 6.1(a), we can assume α represents the front of the cube and α′ the back; β and β′ represent the right and left faces; and γ and γ′ represent the top and bottom (see Figure 6.1(c)).

There are three ways to position a cube (the first cube) at the bottom of the stack with respect to which pair of faces appears on the top and bottom of the cube. Faces γ and γ′ might be in the top and bottom positions (as in Figure 6.1); that is, they might be the “buried” faces. (Hence the four remaining faces are the visible ones involved in the solution of the problem.) On the other hand, faces β and β′ might be buried, or α and α′ might be buried.

Suppose we have selected a position for the first cube. There are now 24 possible positions for the second cube. For example, if face α appears as the front face of the second cube, any of the positions shown in Figure 6.2 might occur. Hence, there are four possible arrangements of this cube for each face selected as the front face. Since a cube has six faces, there are 24 possible placements of the second cube once we have stationed the first cube. Similarly, there are 24 positions for the third cube and 24 positions for the fourth cube. Thus, the total number of arrangements of all four cubes is

3 x 24 x 24 x 24 = 41,472.

Figure 6.2

A trial-and-error solution appears nearly hopeless.

Let us take a specific set of four cubes, shown in Figure 6.3, and attempt to find a solution, if there is one. The symbols R, W, B, G denote the colors red, white, blue, and green.

Figure 6.3

We now bring in graphs, or, more precisely, pseudographs (loops and multiple edges permitted). We represent each cube by a pseudograph of order four. The vertices correspond to the four possible colors. We connect vertices u and v (they need not be distinct) by a number of edges equal to the number of opposite faces in the cube colored u and v. For example, consider Cube 1. As for each cube, the vertices of the pseudograph representing Cube 1 are denoted R, W, B, and G. Since two opposite sides of Cube 1 are colored red and blue, R is adjacent to B in this pseudograph. Since the front and back are colored white and green, W is adjacent to G. Finally, since the top and bottom of Cube 1 are both colored white, we add a loop at W. The four pseudographs shown in Figure 6.4 correspond to the four cubes given in Figure 6.3.

Figure 6.4

We now superimpose the four pseudographs of Figure 6.4, obtaining a pseudograph with 4 vertices and 12 edges. This new pseudograph is shown in Figure 6.5. Each edge is labeled by the number of the cube associated with it.

Let us assume there is a solution to the problem; that is, assume we can stack the four cubes in such a way that all four colors appear on all four sides of the prism. Consider first the front of this prism (and, at the same time, the back of the prism). Each color appears on this front side. If a solution exists, we claim there is a sub-pseudograph H₁ of the pseudograph of Figure 6.5 which represents the front and back of this prism. The sub-pseudograph H₁ contains four edges, with each edge labeled by a different number, 1, 2, 3, or 4. For example, the edge labeled 1 joins the front and back colors of the first cube. Each vertex of H₁ has degree two (a loop at a vertex contributes a degree of two), since a color appears once on the front and once on the back. Hence H₁ is a 2-regular pseudograph of order 4. Similarly, the left and right sides of the prism give rise to a 2-regular pseudograph H₂ of order 4 which is edge disjoint from H₁ (i.e., H₁ and H₂ have no edges in common). Hence, the problem is to determine two such pseudographs H₁ and H₂. In our particular case, there are such pseudographs, shown in Figure 6.6.

Figure 6.5

Figure 6.6

With the aid of H₁ and H₂ of Figure 6.6, we now show how to stack the cubes. We start with the first cube, and place red in the front, say, and blue in the back. Place green on the left, say, and white on the right. (Of course, we could just as well begin by switching left and right, or front and back.) It is convenient to consider the third cube next. Here we place blue in front and green in back and we put white on the left and red on the right. Returning to the second cube, we place white in front and red in back. Red appears on the left, and blue on the right. Finally, for the fourth cube, we set green in front and white in back, while blue is on the left and green on the right.

The solution to “Instant Insanity” suggested here still involves a certain amount of work. With each set of four cubes, we construct a pseudograph of order 4 and size 12 in the manner described above. A solution to the puzzle involves locating two edge-disjoint, 2-regular sub-pseudographs. Once these two sub-pseudographs are found, care must be taken in stacking the cubes. However, this remains considerably simpler than trying all 41,472 arrangements of the four cubes.

Problem Set 6.1

*1. Show that the pseudograph of Figure 6.5 does not contain three edge-disjoint, 2-regular sub-pseudographs of order 4.

2. In the description at the end of this section of how to stack the four cubes, why was the third cube considered before the second cube?

3. Solve “Instant Insanity” with the four cubes pictured in Figure 6.7.

Figure 6.7

4. Solve “Instant Insanity” with the four cubes pictured in Figure 6.8.

Figure 6.8

5. Show that it is possible to color four cubes with four colors, using all four colors on each cube, so that “Instant Insanity” has no solution.

6. Is it necessary that every one of the four colors appear on each cube for “Instant Insanity” to have a solution? Explain.

7. Is it necessary that at least three of the four colors appear on each cube for “Instant Insanity” to have a solution? Explain.

8. Is it necessary that at least two of the four colors appear on each cube for “Instant Insanity” to have a solution? Explain.

9. Is it necessary that at least two of the four colors appear on any cube in order for “Instant Insanity” to have a solution? Explain.

*10. Is it possible to color four cubes with four colors so that “Instant Insanity” has a unique solution? Explain.

11. It was mentioned that there are 41,472 possible arrangements of all four cubes. Exercise 5 implies that for certain sets of cubes, all 41,472 arrangements may fail to yield a solution. What is the maximum number of solutions possible from these 41,472 arrangements?

*12. Is it possible to have an “Instant Insanity” game involving more than four cubes? If so, what restrictions might you place on the cubes to make the game solvable? What restrictions would make the game more interesting?

6.2 The Knight’s Tour

Consider the standard 8-by-8 chessboard, with squares colored alternately white and black. Suppose we place a knight on one of these 64 squares. According to the rules of chess, a knight moves by proceeding two squares vertically or horizontally from its starting square, followed by moving one square in a perpendicular direction. We can now state our game:

The Knight’s Tour Puzzle

FOLLOWING THE RULES OF CHESS, is it possible for a knight to tour the chessboard, visiting every square once and only once, and return to its initial square?

This problem dates back to the time of Euler, although in recent years it has been merchandized as a game. The Knight’s Tour Puzzle is equivalent to determining whether a certain graph G is hamiltonian, where the vertices ui of G correspond to the squares Si of the chessboard, and ui and uj are adjacent if and only if it is possible for a knight to proceed from Si to Sj in a single move. The graph G has 64 vertices and 168 edges, and actually contains several hamiltonian cycles, one of which is shown in Figure 6.9. Thus we can show an affirmative solution to the Knight’s Tour Puzzle.

Figure 6.9

Problem Set 6.2

13. In the graph G of the knight’s moves on the chessboard, determine the length (number of edges) of the shortest path from the vertex of a corner square to the vertex of the diagonally opposite corner square.

14. Investigate the Knight’s Tour Puzzle for a 4-by-4 chessboard.

15. Investigate the Knight’s Tour Puzzle for a 4-by-5 chessboard.

16. Investigate the Knight’s Tour Puzzle for an n-by-n chessboard, where n is odd.

*17. For which other chess pieces does a corresponding tour exist?

6.3 The Tower of Hanoi

The Tower of Hanoi Puzzle

SUPPOSE WE FASTEN THREE PEGS vertically on a stand, and suppose we have eight circular disks, each containing a hole in the middle through which we can pass a peg. Assume each disk has a different radius and, initially, we place all of them on a single peg so that the radii increase as we proceed from the top disk to the bottom (see Figure 6.10). This stack of disks is called the Tower of Hanoi.

Figure 6.10

The puzzle, also known as the Tower of Hanoi (introduced by M. Claus in 1883), is to transfer the disks from the one peg to another in such a way that we move only one disk at a time, and at any stage in the transfer, no disk lies on a smaller disk. Game manufacturers have produced this puzzle under such names as the “Tower of Trouble” and the “Tree Puzzle” (not referring to the graph-theoretic tree).

The procedure for solving this puzzle is as simple to describe for n disks as for 8; thus, we consider a solution for the general case. Suppose all n disks begin on peg A, and assume we require x moves to transfer the top n − 1 disks to peg B, leaving the largest disk on peg A and leaving peg C empty. We may now move the largest disk to peg C. As before, we need x moves to transfer the n − 1 disks on peg B to peg C, solving the problem. This has taken us 2x + 1 moves in all. By considering the puzzle for small n, we see that we require 2n − 1 moves to solve the puzzle, or, equivalently, there are 2n stages in all from the initial to the final position. So, for the 8-disk puzzle, it takes us 2⁸ − 1 = 255 moves.

Thus far, we have said nothing about graphs. As we shall see presently, there is a connection between the solution to the Tower of Hanoi puzzle just presented and hamiltonian graphs. To understand this connection, we first introduce a new class of graphs.

We mentioned the graph of the cube in Exercise 19 in Chapter 3. This is the graph obtained, very naturally, by representing the vertices and edges of the cube in the plane. This cube is known as the 3-dimensional cube or 3-cube. The associated graph is also called the 3-cube. This idea has been generalized to the n-cube Qn, which is the graph of order 2n whose vertices are represented by n-tuples (a sequence of n numbers). Each term of the n-tuple has the value 0 or 1, and two vertices of Qn are adjacent if and only if the corresponding n-tuples differ in only one term. Figure 6.11 shows Q₁, Q₂, Q₃, and Q₄.

Figure 6.11

To represent a solution of the Tower of Hanoi by an n-cube, we number the disks 1, 2, ... , n from the smallest disk to the largest disk: With each step in the solution, we associate an n-tuple as follows. Let the jth position of the disks in the solution to the puzzle be represented by (a1j, a2j, ... , anj), where aij is the number of moves, modulo 2 (meaning 1 + 1 = 0), made by the ith disk. It turns out that the sequence of n-tuples so described, in the order in which they occur in the solution of the puzzle, produces a hamiltonian cycle in Qn.

Figure 6.12

Let us illustrate this relationship between hamiltonian graphs and the Tower of Hanoi with only two disks. The steps in the solution, together with the associated pairs and Q₂, are shown in Figure 6.12.

Problem Set 6.3

18. Draw the graph Q₅ and label the vertices with the appropriate 5-tuples.

19. Solve the Tower of Hanoi puzzle for n = 3, and determine the corresponding hamiltonian cycle of Q₃.

*20. Prove that Qn is hamiltonian for n ≥ 2. (Hint: Use mathematical induction.)

6.4 The Three Cannibals and Three Missionaries Problem

The solution to the Tower of Hanoi Puzzle depends on various positions, or “states,” in the problem. The solution proceeded from an initial state through a sequence of intermediate states to a final state. We used graphs to solve this problem by associating a vertex with each state. Two vertices were joined by an edge whenever we could proceed from one corresponding state to another in a single “move.” Then, in the resulting graph G, we attempted to determine a path from the vertex corresponding to the initial position to the vertex corresponding to the final position. We now consider another problem that falls into this category.

The Three Cannibals and Three Missionaries Problem

THREE CANNIBALS and three missionaries are traveling together, and they arrive at one bank of a river. All three cannibals and all three missionaries want to cross the river to the opposite side. However, the only transportation across the river is a boat which holds at most two people. There is another difficulty: At no time, on neither bank, can the cannibals outnumber the missionaries, for then the missionaries would be in danger. How do they manage to cross the river?

We now present a graphical solution to this problem. By a “position” or “state” here, we mean the situation as it occurs on the first bank. Let c represent the number of cannibals on the first bank and m represent the number of missionaries on the first bank. Hence, the ordered pair (c, m) denotes the state of the system at any one time.

First, we make a few observations. Note that 0 ≤ c ≤ 3 and 0 ≤ m ≤ 3. Hence, there are 16 possible ordered pairs (c, m). However, some of these states are not permitted under the additional restrictions of the problem. For example, in the cases (0, 1), (0, 2), (1, 2), (2, 1), (3, 1), and (3, 2), the cannibals would outnumber the missionaries on the first bank or on the second bank. The permissible ordered pairs are given in Figure 6.13.

Figure 6.13

We must proceed from the ordered pair (3, 3) to (0, 0), but we must do this according to certain rules. If we are at the state (c₁, m₁) and the boat is at the first bank, then we can proceed to the permissible pair (c₂, m₂) provided c₂ ≤ c₁ m₂ ≤ m₁, and

(c₁ + m₁) − (c₂ + m₂) ≤ 2.

If we are at the state (c₁, m₁) and the boat is at the further bank, then we can proceed to the permissible pair (c₂, m₂) provided c₂ ≥ c₁, m₂ ≥ m₁, and

(c₂ + m₂) − (c₁ + m₁) ≤ 2.

Figure 6.14

For example, if we are at the state (2, 2) and the boat is at the first bank, then the next state could be (1, 1) or (2, 0).

It is convenient to introduce a directed signed graph S. The vertices of S correspond to the ten permissible states. We join a positive edge from (c₁, m₁) to (c₂, m₂) if we can proceed from state (c₁, m₁) to state(c₂, m₂) by moving the boat from the first bank to the second bank. We direct a negative edge from (c₁, m₁) to (c₂, m₂) if we can proceed from state (c₁, m₁) to state (c₂, m₂) by moving the boat from the second bank to the first bank. The directed graph S⁺, consisting of the positive edges of S, is shown in Figure 6.14. Observe that there is a positive edge from (c₁, m₁) to (c₂, m₂) if and only if there is a negative edge from (c₂ , m₂) to (c₁ m₁).

Figure 6.15

The object of the problem is to find a directed trail in S from (3, 3) to (0, 0) which alternates positive and negative edges. One such trail is shown in Figure 6.15. Figure 6.16 presents a diagram of the eleven crossings described by the trail of Figure 6.15, showing the number of cannibals and the number of missionaries on each river bank after each crossing.

Figure 6.16

Problem Set 6.4

*21. Show that there is no solution of the Three Cannibals and Three Missionaries Problem requiring less than eleven river crossings.

*22. Would it make sense to talk about the Four Cannibals and Four Missionaries Problem? If so, explain the conditions of the problem and attempt to solve it.

23. Solve the Three Jealous Husbands Problem: Three wives and their three husbands must get to town in a Corvette, which holds only two people. How might they do this so that no wife is ever left with one or both of the other husbands unless her own husband is also present?

24. Solve the Wine Bottle Problem: Three wine bottles have capacities of 8, 5, and 3 liters, respectively. The largest bottle is filled with wine and the other containers are empty. We want to divide the wine into two equal portions using these bottles (which are not graduated) and no others, by pouring successively from one bottle to another. The problem, then, is: How can we obtain 4 liters of wine in the largest bottle and 4 liters in the medium-size bottle, using the fewest possible number of pourings?

Suggestions for Further Reading

We have given only a few examples of the multitude of games and puzzles which can be solved by graphs. Of the several descriptions of “Instant Insanity,” the reader might wish to consult Busacker and Saaty [2, p. 153] and VanDeventer [6]. An excellent description of the Knight’s Tour Problem is presented in Berge [1, p. 109], and Crowe [3] has written an article on the Tower of Hanoi. Problems similar to the Three Cannibals and Three Missionaries Problem are described in Ore [5, p. 30]. For an enormous variety of puzzles involving graphs, however, the reader is recommended to consult the interesting pamphlet written by Fujii [4].

C. Berge, The Theory of Graphs. Wiley, New York (1962).

R. G. Busacker and T. L. Saaty, Finite Graphs and Networks. McGraw-Hill, New York (1965).

D. W. Crowe, “The n-dimensional cube and the tower of Hanoi.” American Mathematical Monthly, 63 (1956), pp. 29−30.

J. N. Fujii, Puzzles and Graphs. National Council of Teachers of Mathematics, Washington D.C. (1966).

O. Ore, Graphs and Their Uses. Random House, New York (1963).

J. VanDeventer, “Graph theory and ‘Instant Insanity’.” The Many Facets of Graph Theory (G. Chartrand and S. F. Kapoor, eds.). Springer-Verlag, Berlin (1969).

Chapter 7

Digraphs and Mathematical Models

As we mentioned in Chapter 1, there are several real-life situations and problems where digraphs are more appropriate mathematical models than graphs. In this chapter we illustrate a few such situations and problems. We include a discussion of a much studied class of digraphs: the tournaments.

7.1 A Traffic System Problem: An Introduction to Orientable Graphs

Suppose we wish to design a traffic system for a small college town in the East. Since the town is small and traffic is ordinarily light, a complex traffic system is not needed; so we agree to make all streets two-way. Certain minimum requirements are necessary; for example, we want to be able to reach any intersection from any other intersection. Also, the street crews make any necessary road repairs during the week. If a crew is repairing a street between two consecutive intersections, thereby blocking off the street, it would be convenient if a motorist could still reach any intersection while the repairs are in progress.

We can easily represent this situation by a graph G. The vertex set of G corresponds to the street intersections, and two vertices are joined by an edge if, in the corresponding two intersections, it is possible to travel from one to the other without passing through a third intersection. The fact that we can reach any intersection in the traffic system from any other intersection implies that G must be connected. If we want to travel between any two intersections even when a street between consecutive intersections is blocked off, then the graph G can have no bridges.

Let us now suppose that on football Saturdays, traffic becomes so heavy we need a different traffic pattern. We decide to convert all streets into one-way streets. Of course, we would like to make this change in such a way that afterwards, using one-way streets, it is still possible to travel (legally) from any intersection to any other intersection. This leads us to our problem.

The traffic System Problem

UNDER WHAT CONDITIONS can a traffic system with all two-way streets be changed to all one-way streets so that in the resulting system, it is possible to travel from any intersection to any other intersection?

In order to solve this problem, we first present a few definitions. Recall that a path in a directed graph is an alternating sequence v₁, a₁, v₂, a₂, v₃, . . . , vn−1, an−1, vn of distinct vertices and arcs such that arc a¡ = (vi, vi+1) for i = 1, 2, ..., n − 1. A digraph D is called strongly connected if for every two distinct vertices u and v of D, there exists a u−v path in D and a v−u path in D.

A connected graph G is called orientable if it is possible to assign a direction to each edge of G (thus changing edges to arcs) to produce a strongly connected digraph D.

We now present a solution to the traffic problem. The solution may be somewhat unexpected, for it states that if a traffic system is suitable for travel during street repairs on weekdays, then it is also suitable for one-way street conversion on football Saturdays, and conversely.

Theorem 7.1

Solution to the Traffic System Problem

A connected graph G is orientable. if and only if G contains no bridges.

Proof

First we prove that if G is orientable, then G cannot contain a bridge. We prove this by contradiction. Thus, let G be an orientable graph and assume, to the contrary, that G contains a bridge, say e = uv. Since G is orientable, we can assign a direction to each edge of G and obtain a strongly connected digraph D. Hence, D contains both a u−v path and a v−u path. Since uv is a bridge, it is an edge of G, so the digraph D contains exactly one of the arcs (u, v) and (v, u). Without loss of generality, we may assume that D contains (u, v). Then, of course, D contains a u−v path, namely u, v. However, D cannot contain a v−u path, since every path from v to u must contain the arc (v, u) because uv is a bridge of G. Therefore G is not orientable, giving us a contradiction. Hence G cannot contain bridges.

Next we verify the converse statement. Assume that G is a connected graph containing no bridges. We prove that G is orientable. Since G contains no bridges, it follows by Theorem 2.5 that every edge of G lies on a cycle. Let C: v₁, v₂, . . . , vn, v₁ be a cycle of G. We assign the edge vnv₁ the direction (vn, v₁), and we assign the edge vivi+1 the direction (vi, vi+1) for i = 1, 2, ... , n − 1. If there exist adjacent, nonconsecutive vertices of C, then the edges between them are directed arbitrarily. If every vertex of G belongs to C, then it is obvious that G is orientable.

Assume there exist vertices of G not belonging to C. Since G is connected, there exists a vertex w₁, not on C, such that w₁vj is an edge of G, where 1 ≤ j ≤ n. Since w₁vj is not a bridge of G, there exists a cycle C₁ : w₁, vj = w₂, w₃, . . . , wm, w₁ in G. We assign wmw₁ the direction (wm, w₁) and we assign w₁w₂ the direction (w₁, w₂). For each i = 2, 3, ... , m − 1 for which wiwi+1 has not already been given a direction, we assign the direction (w¡, wi+1). If an edge joining two vertices of C₁ (or one vertex of C and one vertex of C₁) has not yet received a direction, then a direction can be selected arbitrarily. (See Figure 7.1 for one possibility.)

Figure 7.1

The digraph D₁ constructed in this manner is necessarily strongly connected. If D₁ contains all vertices of G, we are finished. If not, we continue this procedure until all vertices of G have been included in a strongly connected digraph D, which completes the proof. ❚

Example 7.1

Figure 7.2 shows the street system of a small town. A graph G which models this traffic system is also given in Figure 7.2. Since G does not contain a bridge, by Theorem 7.1, G is orientable. Thus, we may assign a direction to each edge of G and obtain a strongly connected digraph. The digraph D of Figure 7.2 is strongly connected.

Figure 7.2

Problem Set 7.1

1. Explain why the proof of Theorem 7.1 is particularly simple if the graph G is hamiltonian.

2. Show that the graph G of Figure 7.2 is hamiltonian. Is there a relationship between the digraph D of Figure 7.2 and your answer to Exercise 1 ?

3. Show that the graph G of Figure 7.3 is orientable. Assign appropriate directions to the edges of G to obtain a strongly connected digraph D.

*4. Let G be an orientable graph, and assign directions to the edges of G to produce a strongly connected digraph D. Suppose that for each edge e of G, we assign the direction opposite to that used in producing D. Let D′ denote the digraph obtained in this way. Is D′ strongly connected? Prove your answer.

Figure 7.3

5. Can a graph with cut-vertices be orientable? Explain.

6. Can an orientable graph G of order at least 2 possess the property that no matter how the edges of G are directed, a strongly connected digraph D always results? Explain.

7. Figure 7.4 shows the street system of a town. Investigate this system in the same way as in Example 7.1.

Figure 7.4

8. Figure 7.5 shows the street system of a town where all streets are two-way. Is it possible to repair the road between intersections A and B so that during the repair work it is possible to drive from any intersection to any other intersection? How do you explain this in view of Theorem 7.1 ?

Figure 7.5

9. Let G be a connected graph of order at least three which has no bridges. Show that it is possible to assign directions to the edges of G so that the resulting directed graph is not strongly connected.

7.2 Tournaments

In the preceding section we saw how directed graphs may serve as models for traffic control problems. As you might expect, there are many other problems for which directed graphs are useful models. Indeed, there is one particular class of directed graphs that we can use to represent a large variety of situations. These are called “tournaments,” the name originating because they represent round robin tournaments. Before investigating some problems relevant to tournaments, we present some pertinent definitions.

A tournament T is a directed graph with the property that for every two distinct vertices u and v, exactly one of (u, v) and (v, u) is an arc of T. That is, a tournament is a digraph which results from assigning directions to the edges of a complete graph.

There is only one tournament of order one and only one tournament of order two (i.e., every two tournaments of order two are isomorphic). There are two non-isomorphic tournaments of order three; they are shown in Figure 7.6. One way of seeing that tournaments T₁ and T₂ of Figure 7.6 are different is by observing that T₂ contains a vertex, namely u₂, which is not adjacent from any other vertex, while T₁ contains no such vertex. It is helpful to consider some definitions involving degrees in directed graphs.

Let D be a directed graph and let v be a vertex of D. The number of vertices of D adjacent from v is called the outdegree of v, denoted by od v; the number of vertices of D adjacent to v is called the indegree of v, denoted by id v. In the tournament T₁ of Figure 7.6, every vertex has the same indegree and the same outdegree, namely 1. In T₂, the vertices have the following indegrees and outdegrees:

od u₂ = id w₂ = 2, od v₂ = id v₂ = 1, od w₂ = id u₂ = 0.

Figure 7.6

A transmitter is a vertex having positive outdegree and zero indegree; a receiver is a vertex having positive indegree and zero outdegree. Thus, in the tournament T₂ of Figure 7.6, vertex u₂ is a transmitter and w₂ is a receiver; tournament T₁ has no transmitters or receivers.

Suppose T is a tournament of order p ≥ 2, and let v be any vertex of T. Then by T − v we mean the directed graph obtained from T by removing v and all arcs incident with v. Necessarily, any two vertices of T − v are joined by exactly one arc, since these two vertices are joined by one arc in T. Hence, if T is a tournament, T − v is also a tournament. This very elementary property of tournaments turns out to be quite useful.

By a round robin tournament we mean a competition among a collection of teams such that every two teams play each other exactly once and no ties are permitted. We can represent every round robin tournament by a tournament T where the vertices of T correspond to the individual teams and where (u, v) is an arc of T if and only if the team corresponding to u defeats the team corresponding to v.

In order to present our first theorem on tournaments, we need some additional definitions. The length of a path P in a digraph is the number of arcs in P. If u and v are two vertices of a directed graph, then the distance d(u, v) from u to v is the length of a shortest u−v path.

Theorem 7.2

Let T be a tournament, and let v be any vertex of T having maximum outdegree. Then the distance from v to any other vertex of T is one or two.

Proof

Let od v = n, and suppose the vertices v is adjacent to are v₁, v₂, . . ., vn. If the order of T is p, then each of the remaining p − n − 1 vertices u₁, u₂, . . . , up−n−1 is adjacent to v, since T is a tournament (see Figure 7.7).

Figure 7.7

For each vertex vi, where 1 ≤ i ≤ n, we have d(v, vi) = 1. We now show that for each vertex uj, where 1 ≤ j ≤ p − n − 1, the distance d(v, uj) = 2. Once this is shown, the proof will be complete.

If each uj is adjacent from some vi, then it is obvious that d(v, uj) = 2. Suppose there is a vertex uk, where 1 ≤ k ≤ p − n − 1, such that no vertex vi 1 ≤ i ≤ n, is adjacent to uk. Then uk is adjacent to all the vertices v₁, v₂, . . . , vn and to the vertex v as well. However, then od uk ≥ n + 1, which is impossible because v has the largest outdegree and od v = n. Hence each uj is adjacent from some vi. ▋

Theorem 7.2 has the following interpretation in round robin tournaments. Suppose several sports teams participate in a round robin tournament (i.e., every two teams play each other and no ties are permitted). Then the winner w (any team with the most victories −there may be more than one winner) has been defeated only by teams which themselves have lost to teams defeated by w.

Another interesting property of tournaments involves hamiltonian paths. A hamiltonian path in a digraph D is a path containing all the vertices of D.

Theorem 7.3

Every tournament contains a hamiltonian path.

Proof

The proof is by induction on the number of vertices p in the tournament. We can actually check out the tournaments with 1, 2, 3, or 4 vertices and verify that each contains a hamiltonian path. So we assume that each tournament of order n,n ≥ 4, contains a hamiltonian path, and we consider a tournament T of order n + 1. We show that T contains a hamiltonian path.

Let v be a vertex of T. As we noted earlier, T − v is a tournament of order n. By the induction hypothesis, T − v contains a hamiltonian path, say P : v1, v₂,..., vn. Now if (v, v₁) is an arc of T, then T contains the hamiltonian path v, v₁, v₂,..., vn. Also, if (vn, v) is an arc of T, then T contains the hamiltonian path v1, v₂,..., vn, v.

Suppose (v₁, v) is an arc of T. If all the vertices v₁, v2, . . . , vn are adjacent to v, then T contains a hamiltonian path because (vn, v) is an arc of T. If not all the vertices v₁, v₂, . . . , vn are adjacent to v, then there must be a vertex vi, where 1 ≤ i ≤ n − 1, such that (vi, v) and (v, vi+1) are arcs of T (see Figure 7.8). However, then

v₁, v₂, . . . , vi, v, vi + 1, vi + 2, . . . , vn

is a hamiltonian path. ❚

Figure 7.8

This result implies that at the conclusion of a round robin tournament, it is possible to rank the n teams as, say, T₁, T₂, T₃, . . . , Tn, where team T₁ has defeated T₂, team T₂ has defeated T₃, etc.

Problem Set 7.2

10. How many non-isomorphic tournaments of order 4 are there? Draw them all.

11. Define: Tournament T₁ is isomorphic to tournament T₂.

12. Let U be a nonempty proper subset of the vertex set of a tournament T. Show that the removal of U from T results in a tournament.

13. If a graph G of size q has vertices v₁, v₂, . . . , vp, then we know that

Suppose a digraph D of size q has vertices v₁, v₂, . . . , vp.

What does od vi equal?

What does id vi equal?

What values do we get in (a) and (b) if D is a tournament?

14.

Give an example of a digraph D and two vertices u and v of D such that d(u, v) is not defined.

Under what conditions does a digraph D have the property that for every two vertices u and v of D, both d(u, v) and d(v, u) are defined?

15. Let u and v be distinct vertices of a tournament T such that both d(u, v) and d(v, u) are defined. Show that d(u, v) ≠ d(v, u).

16.

In Exercise 12 of Chapter 2 we defined a graph G (of order p ≥ 2) to be perfect if no two of its vertices have equal degrees. What would be a reasonable definition of a “perfect digraph”? According to your definition, are there any perfect digraphs?

What would be an appropriate definition of “regular digraph”? According to your definition, is there a regular tournament of order 4?

17.

If five teams play in a round robin tournament, show that it is possible for all five teams to tie for first place.

If six teams play in a round robin tournament, show that it is not possible for all six teams to tie for first place.

*18. Theorem 7.2 states that if v is a vertex of maximum outdegree in a tournament T, then the distance from v to any other vertex of T is either one or two. Let n denote the number of vertices of T whose distance from v is one, and let m denote the number of vertices of T whose distance from v is two. Which of the following relations are possible: (i) n > m, (ii) n = m, (iii) n < m?

19. Theorem 7.3 implies that we may rank teams in a round robin tournament as T₁ T₂,..., Tn, where team Ti defeats team Ti+1 for i = 1, 2, . . . ,n − 1.

Give an example of a round robin tournament where such a ranking may give a true ordering of the teams.

Give an example of a round robin tournament where such a ranking may give a misleading ordering.

20. Prove that every tournament has at most one transmitter and at most one receiver.

7.3 Paired Comparisons and How to Fix Elections

There are many instances in our daily lives when we must make a choice among certain options. For example, a person may be planning to buy an automobile and must decide among a hardtop, sedan, van, or station wagon. Let us suppose that the preferences of a certain Mr. X are as follows (in order):

van

hardtop

station wagon

sedan

This list of preferences may also be given by the tournament T of Figure 7.9.

Figure 7.9

If we use a tournament T as a model of preferences, then the vertices represent the options and an arc is directed from vertex u to vertex v if the option corresponding to u is preferable to the option corresponding to v. If the tournament contains no cycles, then the choices made are consistent. For example, in the tournament T of Figure 7.9, we see that Mr. X prefers the van over the hardtop and prefers the hardtop over the station wagon. This suggests that Mr. X should prefer the van over the station wagon, which, indeed, he does.

As long as such tournaments of paired comparisons are consistent, we can reach some fair decisions. However, if a given tournament is inconsistent, then someone may be able to “swing” an interpretation in his favor by clever manipulation. We illustrate this.

Example 7.2

The Mathematics Department of a University has a decision-making committee with a place for one student to serve as a member. Three students, Frank (a freshman), John (a junior), and Gwen (a graduate student), are selected as a committee of three to determine which student should serve on this committee. They decide that the freshman, sophomore, junior, and senior classes, and the graduate students, should each nominate one student for membership on this faculty-student committee.

John volunteers to act as chairman of the three students, and begins discussions to decide which of the five students should be chosen. After some time, John observes that he. Frank, and Gwen have the following preferences:

John | Frank | Gwen
1. junior | 1. freshman | 1. graduate
2. senior | 2. sophomore | 2. senior
3. graduate | 3. junior | 3. sophomore
4. freshman | 4. senior | 4. freshman
5. sophomore | 5. graduate | 5. junior

These preferences can be shown by the tournaments in Figure 7.10 (page 164).

We can establish a cumulative tournament based on the tournaments (i.e., the preferences) of Frank, John, and Gwen. For example, both John and Frank prefer the freshman to the sophomore, while Gwen prefers the sophomore to the freshman. Thus, we conclude that the committee of Frank, John, and Gwen prefer the freshman to the sophomore. The cumulative preference tournament is given in Figure 7.11 (page 165).

John observes that the cumulative preference tournament is inconsistent. Knowing this, he plans his strategy. He proposes that since no two of the committee of three agree on the student representative, they should proceed by a process of elimination. They take a vote between the freshman and the sophomore, and the freshman wins. Next, they vote between the junior and the senior, and the junior wins. Hence, the sophomore and the senior have been eliminated. They next vote between the graduate student and the freshman, and the graduate student wins. Finally, they vote between the junior and the graduate student, and the junior (who just happens to be John’s first choice) wins and is therefore chosen as student representative.

Figure 7.10

Figure 7.11

Example 7.3

A rarity for the town of Torrence! For the first time ever, three candidates are running for the office of mayor, namely Councilmen Adams, Beane, and Carter. The town elections officer does not know quite how to proceed with the election. Past records indicate that only one or two people have run for mayor in previous years, so there is no precedent to go by. The elections officer decides to ask for advice from the intelligent (and often unscrupulous) Professor Dixon, who teaches at the University only a few miles away. Professor Dixon says that before giving an opinion on this matter he would like to think about it for a few days. The Professor believes that the election will be close, so he decides to have two of his students conduct a poll of the voters of Torrence.

After two days of extensive polling, Professor Dixon’s students report the following results:

Of the 2500 registered voters of Torrence, two-thirds indicate that they plan to vote on Election Day.

Councilman Adams is the first choice of 35% of those surveyed, and nearly all of these pick Carter as their second choice.

Councilman Beane is the first choice of 30%, and nearly all of these have Carter as their second choice.

Councilman Carter is the first choice of 25%, and nearly all of these pick Beane as their second choice.

The remaining 10% are undecided.

Professor Dixon studies the results of this survey—and smiles. He sees how he can make some extra money. He calls Councilmen Adams, Beane, and Carter in turn and tells each one that for the right amount of money, he will see to it that he will be elected mayor. While waiting for their responses, Professor Dixon prepares the following three memos, of which only one will be given to the elections officer.

Memo A. The natural thing to do is to hold the election on Election Day, and declare the candidate with the highest number of votes the winner. Any kind of runoff election would cost the town additional money and would serve no purpose.

Memo B. The natural thing to do is to hold a preliminary election. The candidate with the lowest vote total is eliminated, and the final election is between the two top vote-getters from the preliminary election. This procedure assures that the newly elected mayor receives votes from a majority of the voters.

Memo C. The natural thing to do is to hold a preliminary election asking the voters to determine whom they least want as mayor. This person is then eliminated and the final election is held between the remaining two candidates.

Shortly after Professor Dixon prepares these memos, the police arrive at his home and arrest him for attempting to solicit bribes from the three councilmen. The memos are never delivered. The elections officer decides to hold a single election. As expected, Adams is the winner. The final vote is:

Adams | 600
Beane | 500
Carter | 400

Problem Set 7.3

21. Give an example of a choice of options you have had recently which can be represented by a tournament.

22. With reference to Example 7.2, show how you could have altered the order of voting so that the student representative is

the freshman;

the sophomore;

the senior;

the graduate student.

23. Again, referring to Example 7.2, how should the student representative have been selected so as to reflect the preferences of Frank, John, and Gwen?

*24. A directed graph D is called transitive if whenever (u, v) and (v, w) are arcs of D, then (u, w) is also an arc of D. Show that a tournament T is transitive if and only if T has no cycles. (Thus, a tournament representing paired comparisons is consistent if and only if it is transitive.)

25. With reference to Example 7.3, who would have been elected mayor if Memo A had been delivered? Describe the election by means of a tournament of order 3.

26. In Example 7.3, who would have been elected mayor if Memo B had been delivered? Describe the election by means of a tournament of order 2.

27. In Example 7.3, who would have been elected mayor if Memo C had been delivered? Describe the election by means of a tournament.

28. With reference to Example 7.3:

In your opinion, in what order should the memos be listed to go from fairest to least fair?

In your experience, which memo would a community most likely follow?

29. Referring again to Example 7.3, construct a tournament T with vertices A, B, and C (Adams, Beane, and Carter) such that arc (u, v) belongs to T if, in a choice between candidates u and v, more voters prefer u than v. By this criterion, who should be elected mayor of Torrence?

30. In Example 7.3, who, in your opinion, should be elected mayor? Explain.

31. Ten sports broadcasters vote to decide the final rankings of college football teams by assigning points to the teams (10 to the best, 1 to the tenth). Nine of the broadcasters think State is best and Central is second. The tenth broadcaster (who went to Central) would like to see his alma mater ranked high. How could he affect the outcome?

Suggestions for Further Reading

The book by Harary, Norman, and Cartwright [4] gives a wealth of information on directed graphs and their applications, including discussions on voting. An interesting pair of articles on voting was written by Colman and Pountney [1,2]. Numerous facts about tournaments can be obtained from the survey article written by Harary and Moser [3]. A considerably more advanced book on tournaments has been written by Moon [5], who also wrote an interesting article [6] on voting.

A. M. Colman and I. Pountney, “Voting paradoxes: a Socratic dialogue.” The Political Quarterly. 46(1975), pp. 186–190.

A. M. Colman and I. Pountney, “Voting paradoxes: a Socratic dialogue (II).” The Political Quarterly. 46 (1975), pp. 304–309.

F. Harary and L. Moser, “The theory of round robin tournaments.” American Mathematical Monthly. 73 (1966), pp. 231–246.

F. Harary, R. Z. Norman and D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs. John Wiley & Sons, New York (1965).

J. W. Moon, Topics on Tournaments. Holt. Rinehart, and Winston, New York (1968).

J. W. Moon, “A problem on rankings by committees.” Econometrica, 44 (1976), pp. 241–246.

Chapter 8

Graphs and Social Psychology

The investigation of relationships between people within a group is a branch of social psychology called group dynamics. Signed graphs and signed digraphs can serve as appropriate mathematical models in this area, with vertices representing the individuals of a particular group and positive and negative edges (or arcs) representing “positive” and “negative” relations. For the most part, graphs and digraphs have been used in social psychology primarily to lend clarity to situations rather than to aid in solving problems. In this chapter we consider some of the situations and problems that occur in social psychology.

8.1 The Problem of Balance

Suppose we have a group of people such that every two individuals are either (i) friendly toward each other; (ii) unfriendly toward each other; or (iii) indifferent toward each other. We refer to such a group of people with such relations between them as a social system. We may also use this term if “friendly” and “unfriendly” are replaced by the more general terms “positive relation” and “negative relation,” respectively.

A social system is called balanced if all relations between people are positive, or if we can divide the group into two subgroups so that every positive relation occurs between individuals in the same subgroup, and every negative relation occurs between individuals in different subgroups. No additional restriction applies if neither a positive nor a negative relation (i.e., indifference) exists between individuals in the same or different subgroups. Some social psychologists have hypothesized a “tendency toward balance” in any social system, implying that an unbalanced system contains excessive stress or tension. The system tends to adjust so as to relieve this tension, by such acts as, for example, certain individuals within the group changing their points of view. Thus there is a tendency for the group to split into two factions such that within each faction the only relations are positive, and between factions the only relations are negative.

The concept of balance may be likened to a two-party system of government, where those people favoring a given party constitute the members of a faction. According to some social psychologists, then, such a system yields the greatest harmony within a social system.

We can represent a social system by a signed graph S whose vertices correspond to the individuals. A positive edge joins two vertices if there is a positive relation between the corresponding individuals, and a negative edge joins two vertices if there is a negative relation between the corresponding individuals. Indifference between two individuals is indicated by the lack of any edge joining the corresponding vertices. The following definition is now natural. A signed graph S is balanced if its vertex set can be partitioned into two subsets (one of which may be empty) so that each edge joining two vertices in the same subset is positive, while each edge joining vertices in different subsets is negative. It follows that balanced signed graphs are precisely those signed graphs which represent balanced social systems. In Figure 8.1, the signed graph S₁ is balanced, while the signed graph S₂ is unbalanced.

To verify that the signed graph S₁ of Figure 8.1 is balanced, consider the partition V(S₁) = V₁ ∪ V₂, where V₁ = {u₁, u₂, u₃} and V₂ = {u4, u₅}. Every edge joining two vertices of V₁ or two vertices of V₂ is positive, while every edge joining a vertex of V₁ with a vertex of V₂ is negative. Therefore, S₁ is balanced.

Figure 8.1

We show by using a contradiction argument that S₂ is unbalanced. Suppose S₂ is balanced. Then there exists a partition V(S₂) = V₁ ∪ V₂ such that every edge connecting two vertices of V₁ or two vertices of V₂ is positive, while every edge between a vertex of V₁ and a vertex of V₂ is negative. Consider the vertex w₁. Without loss of generality, we may assume that w₁ ∈ V₁. Since w₁w₂ is a negative edge, w₂ ∈ V₂, and since w₁w₆ is a positive edge, w₆ ∈ V₁. However, w₂ ∈ V₂, w₆ ∈ V₁, but w₂ w₆ is a positive edge, a contradiction. Therefore, S₂ is unbalanced.

Consider a social system consisting of three individuals A, B, and C such that no indifference exists between any two people. There are four such social systems; these are illustrated by the signed graphs of Figure 8.2. Figure 8.2(a) shows total harmony in the system. In Figure 8.2(b), individual C finds himself in the untenable position of agreeing with A and disagreeing with B, while A and B agree with each other. In Figure 8.2(c), B and C still disagree with each other, but now C disagrees with A as well as with B, while A and B still side with each other. There is no inconsistency with this arrangement. Figure 8.2(d) shows total disagreement among A, B, and C.

Figure 8.2

A path or cycle in a signed graph is called positive if it has an even number of negative edges, and is called negative otherwise. Thus, a path with no negative edges is positive.

We now prove two theorems giving necessary and sufficient conditions for a signed graph to be balanced.

Theorem 8.1

A signed graph S is balanced if and only if for every two vertices of S, all paths joining them have the same sign.

Proof

Let S be a balanced signed graph. We show that for each pair of vertices, all paths joining them have the same sign. If S contains only positive edges, then all paths are positive and the result follows immediately. If not all edges of S are positive, then we can partition the vertex set of S into two nonempty sets V₁ and V₂ such that an edge joining two vertices of Vi, i = 1, 2, is positive, while every edge joining a vertex of V₁ to a vertex of V₂ is negative. We now observe that any path joining two vertices of V₁ has an even number of negative edges, since whenever the path proceeds from V₁ to V₂ (using one negative edge), it must return to V₁ (thereby using another negative edge). By similar reasoning, every path joining two vertices of V₂ is positive, and every path joining a vertex of V₁ to a vertex of V₂ is negative.

Conversely, assume that S is a signed graph with the property that for each pair of vertices, all paths joining them have the same sign. We show that S is balanced. We can assume that S is connected, for if S is not connected and we can show that every component of S is balanced, it then follows that S itself is balanced. Let v be a vertex of S, and define the set V₁ to consist of v and all vertices x such that a positive path exists between x and v. If S has only positive edges (so that S is balanced), then V₁ contains all vertices of S.

Suppose that S has some negative edges, and let V₂ = V(S) − V₁. There can be no positive edge of the type v₁v₂, where v₁ ∈ V₁ and v₂ ∈ V₂, for this implies the existence of a positive path between u and v₂ or a negative path between v and v₁, contradicting the facts that v₂ ∉ V₁ and v₁ ∈ V₁.

There can be no negative edge of the type uw, where u, w ∈ V¡, i = 1, 2, for suppose uw is negative. All paths from v to u have the same sign as those paths from v to w. If P is a path between v and u not containing w, then P followed by uw followed by w is a path between v and w having the opposite sign of P. If every path between v and u contains w, then there exists a v−w path P’ not containing u. We can then produce a path P″ between v and u by taking P′ followed by wu and then u. The paths P′ and P″ have opposite signs. In either case, a contradiction arises, so uw must be positive.

Thus, V₁ ∪ V₂ is an appropriate partition so that S is balanced. ▋

The following characterization of balanced signed graphs is now rather immediate.

Theorem 8.2

A signed graph S is balanced if and only if every cycle of S is positive.

Proof

Let S be a balanced signed graph, and suppose S has a negative cycle C. The cycle C therefore contains an odd number of negative edges. Let u and v be any two distinct vertices of C. The cycle C produces two edge-disjoint u−v paths, one necessarily containing an even number of negative edges, and the other containing an odd number of negative edges. This implies that there is a negative path as well as a positive path joining u and v, but this contradicts Theorem 8.1. Hence, every cycle of S is positive.

Assume now that S is a signed graph in which every cycle is positive. If S is not balanced, then by Theorem 8.1, there exist two vertices u and v and two u−v paths P′ and P′ such that one path is positive and the other path is negative. It then follows that P′ and P″ together produce a negative cycle, contradicting the hypothesis. Thus, S is balanced. ❚

Example 8.1

Consider a social system where friendliness or unfriendliness occurs between certain pairs of individuals. Assume there is a rumor which has two basic forms, one true and one false. Suppose anyone would tell the rumor to a friend in the same form he had received it, but would change the form if he were to pass the rumor to someone with whom he is unfriendly. If the system is balanced, each person will hear only one version of the rumor regardless of how it reached him; also, the person who started the rumor will hear it returned to him in the same form as he originally knew it.

Problem Set 8.1

1. Suppose we have a social system in which every two individuals dislike each other. Is this system balanced or unbalanced?

2. Suppose we have a social system in which every two individuals are indifferent toward each other. Is this system balanced or unbalanced?

3. Let S be a signed graph with no cycles whatsoever. Is it possible to determine whether S is balanced or unbalanced? Explain.

4. Show that in Figure 8.3 the signed graph S₁ is balanced and the signed graph S₂ is not balanced.

Figure 8.3

*5. Prove that if S₁ S₂, . . . , Sn are connected balanced signed graphs, then the disconnected signed graph S, having S₁, S₂, . . . , Sn as components, is balanced.

*6. Let S₁ and S₂ be two connected balanced signed graphs, and let S be the connected signed graph obtained by “identifying” a vertex of S₁ with a vertex of S₂ (i.e., a vertex of S₁ is combined with a vertex of S₂ to form one vertex of S). Prove that S is balanced.

*7. In the proof of Theorem 8.2, supply the details of the fact that the paths P′ and P″ produce a negative cycle.

8. What signed graph would represent a “love triangle”? Is this signed graph balanced or unbalanced? If you answered “unbalanced,” how would you interpret a tendency toward balance? If you answered “balanced,” what assumptions are you making?

9. A city suburb contains a very closely knit neighborhood. A new family of lower social status moves into this neighborhood. At first, all of the original neighbors have nothing to do with this family, but then one of the original families makes friends with the newcomers. What might happen in the rest of this neighborhood?

8.2 The Problem of Clustering

Figure 8.2(d) illustrated a social system containing three individuals in which only negative relations exist. By definition, such a system is unbalanced, implying that it is unnatural and susceptible to inner tension. However, we must emphasize that this is only a point of view among some social psychologists. A related but alternate theory is to anticipate a “clustering” of people into factions or clusters (not necessarily two) where the only relations occurring between individuals in the same cluster are positive, and the only relations occurring between individuals in different clusters are negative. There may be indifference between some individuals. Social systems possessing this property are called clusterable. Clusterable social systems are therefore generalizations of balanced social systems. The signed graph of Figure 8.2(d) represents a clusterable social system with three clusters.

It is now convenient to define clusterable signed graphs. A signed graph S is said to be clusterable if its vertex set can be partitioned into subsets, called clusters, so that every positive edge joins vertices within the same subset and every negative edge joins vertices in different subsets.

We can now present a characterization of clusterable signed graphs.

Theorem 8.3

A signed graph S is clusterable if and only if S contains no cycle with exactly one negative edge.

Proof

Assume that S is a clusterable signed graph. We show that no cycle of S has exactly one negative edge. Let C be a cycle of S. If C contains vertices from a single cluster, then all edges of C are positive. If C contains vertices from two or more clusters of S, then C contains at least two edges joining different clusters, i.e., at least two negative edges. However, in either case, C does not contain exactly one negative edge.

Conversely, let S be a signed graph containing no cycle with exactly one negative edge. Let u and v be any elements of the vertex set V of S. Now we define a relation R on V such that (u, v) ∈ R if u = v or if u and v are joined by a path whose edges are all positive. The relation R is reflexive, symmetric, and transitive; that is, R is an equivalence relation. Recall that the equivalence class [x], where x ∈ V, consists of all vertices related to x. By Theorem A.2 in the Appendix, the equivalence classes determined by R form a partition of V. We show that these equivalence classes are clusters of S, so that S is clusterable.

There can be no positive edge joining vertices u and v in different equivalence classes, for if there were, we would have a u−v path all of whose edges (actually only one edge) are positive, so that u is related to v, and u and v belong to the same equivalence class. Also, there can be no negative edge joining vertices y and z in the same equivalence class, because since y and z belong to the same equivalence class, there exists a y−z path P all of whose edges are positive. However, the path P together with the negative edge yz produces a cycle having exactly one negative edge, contradicting our definition of S. Therefore, the equivalence classes serve as clusters and S is a clusterable signed graph. ▋

Figure 8.4

Figure 8.4 shows a signed graph which is clusterable but not balanced. The clusters of this signed graph are

V₁ = {v₁, v₅, v₆, v₉}, V₂ = {v₂, v₃, v₄},

and

V₃ = {v₇, v₈}.

Problem Set 8.2

10. Show that the signed graph of Figure 8.4 is clusterable by verifying that the given clusters possess the desired properties.

*11. Show that if S is a disconnected signed graph and every component of S is clusterable, then S is clusterable. Determine the minimum number of clusters of S in terms of the minimum number of clusters in the components of S.

12. Give a real-life example of a social system in which clustering is more appropriate than balance.

13. A married couple obtain a divorce. Prior to the divorce, many of the friends and relatives of the man were friends with many of the friends and relatives of the woman. Describe a possible social system (in terms of balance and clustering) consisting of these people after the divorce. Give an explanation with your answer.

14. A clique in a signed graph S is defined as a complete subgraph S₀ of S such that all edges of S₀ are positive. A clique in a social system may be described as a closely knit group of people with common interests.

What is the connection between cliques and clusters in a clusterable signed graph?

Are you aware of cliques among people you know? Are you a member of a clique?

8.3 Graphs and Transactional Analysis

We have already noted that graphs are quite useful in visualizing certain situations occurring in social psychology; however, theorems about graphs have not been particularly important in this area. Another pictorial use of graphs in social psychology is explored in this section.

In social psychology, a transaction consists of two parts: the transactional stimulus and the transactional response. In any gathering of two or more people, eventually one of them will recognize the presence of the others. (This could take the form of the person speaking, smiling, nodding, etc.) This is the transactional stimulus. A reaction by one of the other people to this stimulus is called the transactional response. As the term suggests, transactional analysis is the analysis or examination of transactions, particularly between a specific individual and other people.

The psychologists and psychiatrists who deal in transactional analysis believe that each person exists in one of three states, referred to as the Parent, the Adult, and the Child. In terms of graphs, it is customary in these circumstances to represent an individual as a “vertex triple” (as shown in Figure 8.5), with P, A, and C denoting the Parent, the Adult, and the Child, respectively.

Figure 8.5

The Parent consists of the recordings or recollections of the external stimuli the individual experienced in his early life, ordinarily that period prior to attending school. Since the most pronounced experiences of this time are his parents (or guardians), the term Parent is employed. The Parent state includes the numerous rules laid down by the parents, consisting of “what to do” and “what not to do.” The significant feature of these recordings is that they are retained as the truth.

The Child consists of recordings of the responses to experiences an individual encountered in his early life. Most of these reactions take the form of feelings, since oral communication is limited in the early years. There are many demands put on a young child, and the child does not understand why these requirements are placed on him. The Child often contains feelings of anger, rejection, and frustration. However, it often contains such positive reactions as curiosity.

At some point in life, the individual has more control of his responses and is able to make decisions on his own, rather than do things the way it was shown to him or the way he wished it could be. The Adult, therefore, is the state that makes decisions based on various information gathered. This differs from the Parent, where reactions are by imitation, or the Child, where reaction is rapid and unthinking.

We are primarily concerned with relations between individuals and the states they may be in at a given instant. We shall illustrate this by examples, at the same time giving the appropriate model in terms of graphs (actually digraphs).

The most enjoyable type of transaction is that referred to as complementary. In this kind of transaction, two individuals A and B are in states α and β, respectively. Furthermore, A addresses the β state of B, and B addresses the α state of A. We represent this transaction as a (directed) cycle of length two between two states in the graphical model. We consider this type first.

Example 8.2

Let us examine three conversations going on between certain pairs of individuals at an airport. First, two men begin a conversation.

Mr. A: | Excuse me. What time do you have?
Mr. B: | It’s 10:40. Are you taking this flight?
Mr. A: | Yes, I’m going to San Francisco.
Mr. B: | I’m going to Denver. I believe it’s the only stop between here and San Francisco.
Mr. A: | That’s right. I take this flight quite regularly.

The transaction between Mr. A and Mr. B is an Adult− Adult transaction (see Figure 8.6).

Figure 8.6

A gentleman and a lady begin a conversation.

Ms. C: | Why don’t they let us on the plane? I want a seat next to the window.
Mr. D: | We’ll probably be late. I’ve never taken a plane that has left on time.
Ms. C: | I haven’t either. I don’t know why they bother to list departure times.
Mr. D: | If I ran my business this way, I’d be broke.

This is an example of a Parent-Parent transaction and is illustrated in Figure 8.7.

Figure 8.7

Next we listen to a husband and wife waiting for their flight.

Mrs. E: | Don’t shake so much. It’s embarrassing.
Mr. E: | I can’t help it. I get this way whenever I think of flying.
Mrs. E: | It’s safer in a plane than in a car—especially the way you drive.
Mr. E: | Don’t yell at me! You make me nervous.
Mrs. E: | Stop whimpering!

This is an example of a Parent-Child transaction (see Figure 8.8).

Figure 8.8

We next consider noncomplementary transactions. These types of transactions cause difficulties between people, result in communication breakdowns, and can lead to a need for therapy by a psychologist or psychiatrist. In representing a noncomplementary transaction between two individuals by using a digraph, no cycle is created: only a (directed) path of length two, or two paths of length one each.

Example 8.3

We consider three situations which result in noncomplementary transactions. In each case, two dormitory roommates are having a discussion that quickly leads to a lack of communication.

In the first case, both students are in their Parent state and address the other individual’s Child state (see Figure 8.9).

Mr. A: | Why don’t you pick up your clothes? This room’s a mess.
Mr. B: | I pay half the rent—I can do what I want. Your friends are what make this room a mess.

Figure 8.9

In the next room, one student is in the Adult state and the other is in the Child state (see Figure 8.10).

Mr. C: | What are you studying tonight?
Mr. D: | Math! Stupid math! Why don’t they ever write a math book that makes sense? Who needs math, anyway?

Figure 8.10

In the final situation, one student is in his Adult state while the other is in his Parent state (see Figure 8.11).

Mr. E: | I’ve decided to major in math.
Mr. F: | What makes you think you’re smart enough to major in anything?

Figure 8.11

Problem Set 8.3

15. Give two responses for each of the following statements, one response causing a complementary transaction and the other a noncomplementary transaction. Draw the appropriate digraphs.

(a) | Mr. A: | This dormitory food is terrible. I’m not eating it, no matter what.
(b) | Mr. C: | Girls aren’t any good in mathematics.
(c) | Miss E: | I dropped my pen behind your desk. Would you pick it up for me, please?

16. Give examples of two transactions such that one can be represented by the digraph in Figure 8.12(a) and the other can be represented by Figure 8.12(b).

Figure 8.12

17. A hockey player telephones a girl, asking her for a date. Give four sample conversations: two complementary and two noncomplementary transactions. Draw the corresponding digraphs.

Suggestions for Further Reading

Heider [5] is credited with developing much of balance theory, while Davis [3] initiated the idea of clustering. Two other papers of interest on these topics are by Cartwright and Harary [2] and by Riley [6].

Berne is considered the originator of transactional analysis (see [1], for example); however, a popular book on this subject has been written by Harris [4].

E. Berne, Games People Play. Grove Press, New York (1964).

D. Cartwright and F. Harary, “Structural balance: a generalization of Heider’s theory.” Psychological Review, 63 (1956), pp. 277–293.

J. A. Davis, “Clustering and structural balance in graphs.” Human Relations, 20 (1967), pp. 181–187.

T. A. Harris, I’m OK—You’re OK: A Practical Guide to Transactional Analysis. Harper and Row, New York (1967).

F. Heider, “Attitudes and cognitive organization.” Journal of Psychology, 21 (1946), pp. 107–112.

J. E. Riley, “An application of graph theory to social psychology.” The Many Facets of Graph Theory (G. Chartrand and S. F. Kapoor, eds.). Springer-Verlag, Berlin (1969), pp. 275−280.

Chapter 9

Planar Graphs and Coloring Problems

Two major concepts in graph theory are planarity and chromatic number. In this chapter we consider two problems whose solutions illustrate these concepts. We then discuss a problem which combines both ideas: the famous Four Color Problem.

9.1 The Three Houses and Three Utilities Problem: An Introduction to Planar Graphs

We begin by stating the problem which concerns us in this section.

The Three Houses and Three Utilities Problem

SUPPOSE WE HAVE three houses and three utility outlets (electricity, gas, and water) situated as shown in Figure 9.1. Is it possible to connect each utility with each of the three houses without the lines or mains crossing?

Figure 9.1 shows one way we might try to connect each utility with each house; however, this procedure evidently fails, since there appears to be no way of connecting the third house to the water outlet without crossing some line or main. This implies that either this procedure for connecting the houses and utilities is incorrect, or there is no way of doing it.

To find a solution to this problem, we once again turn to graph theory. We can represent the situation described in the Three Houses and Three Utilities Problem by a graph whose vertices correspond to the houses and utilities, and where an edge joins two vertices if and only if one vertex denotes a house and the other vertex denotes a utility. This bipartite graph is denoted by K(3, 3), indicating that the vertex set is partitioned into two sets of three vertices each, and all allowable edges are drawn. The graph K(3, 3) is shown in Figure 9.2.

Figure 9.1

Figure 9.2

The concept we are primarily interested in is planar graphs. A planar graph is a graph that can be drawn in the plane in such a way that no two edges intersect except at a vertex. For example, the graph G of Figure 9.3(a) is drawn with intersecting edges, but it is a planar graph because G can be drawn, as in Figure 9.3(b), so that no edges intersect.

The Three Houses and Three Utilities Problem can now be restated in the language of graph theory: Is K(3, 3) a planar graph?

Before answering this question, we need to establish a few basic results about planar graphs. A planar graph already drawn in the plane so that no two edges intersect is referred to as a plane graph. Thus, the graph of Figure 9.3(a) is not a plane graph, but the graph of Figure 9.3(b) is a plane graph.

Figure 9.3

Let G be a plane graph and consider the parts of the plane remaining after we remove the edges and vertices of G. These connected pieces of the plane are called regions of G. The vertices and edges of G which are incident with a region R make up the boundary of R. Let us illustrate these concepts. In Figure 9.4 the graph G₁ has three regions, G₂ has one region, and G₃ has six regions. The boundary of the region R₁ of G₃ consists of the vertices v₂, v₃, and v₄ and the edges v₂ v₃, v₂ v₄, and v₃ v₄; the boundary of R₆ consists of the vertices v₁, v₂, v₃, v₅, v₆, and v₇ and the edges v₁ v₂, v₂ v₃, v₃ v₅, v₅ v₆, v₆ v₇, and v₂ v₇. The region R₆ is called the exterior region of G₃. Every plane graph always has exactly one exterior region.

The plane graph G₁ of Figure 9.4 has p = 4 vertices, q = 5 edges, and r = 3 regions; G₂ has p = 5, q = 4, and r = 1; while G₃ has p = 7, q = 11, and r = 6. Observe that in all three cases, p − q + r = 2. This is no mere coincidence, as we now show.

Figure 9.4

Theorem 9.1

Let G be a connected plane graph with p vertices, q edges, and r regions. Then

p − q + r = 2.

Proof

We use induction on q. If q = 0, then p = 1 and r = 1, so

p − q + r = 1 − 0 + 1 = 2,

and the result is true.

Assume the result holds for all connected plane graphs with k − 1 edges, say, and let G be a connected plane graph with k edges. Suppose that G has p vertices and r regions. We show that p − k + r = 2.

If G is a tree, then by Theorem 4.2, p = k + 1 and, of course, r = 1, so

p − q + r = (k + 1) − k + 1 =2

and the formula follows. If G is not a tree, then since G is connected, G contains cycles. Let e be an edge lying on a cycle of G, and consider the plane graph G − e (which is also connected). The two regions incident with e in G produce one region in G − e. Therefore G − e has p vertices, k − 1 edges, and r − 1 regions. We can apply our induction hypothesis to conclude that

p − (k − 1) + (r − 1) = 2

or

p − k + r = 2,

which is what we wanted to prove. ▋

Theorem 9.1 is a classical theorem of graph theory; in fact, the result is due to Euler. We can now verify another useful result, whose proof involves a rather tricky counting argument.

Theorem 9.2

Let G be a connected planar graph with p vertices and q edges, where p ≥ 3. Then

q ≤ 3p − 6.

Proof

We first note that the result is true for p = 3, since every graph of order three has size at most three. Hence, we assume p ≥ 4. We draw the graph G as a plane graph, and denote the number of regions of G by r. For each region R of G, we determine the number of edges lying on the boundary of R, and then sum these numbers over all regions of G. We call this number N. Since there are at least three edges belonging to the boundary of every region, it follows that N ≥ 3r. On the other hand, the number N counts every edge of G once or twice; that is, N ≤ 2q. Hence,

3r ≤ N ≤ 2q or 3r ≤ 2q.

This says that −r ≥ −2q/3. Now by Theorem 9.1, we know that

p − q + r = 2, or p = q − r + 2.

Therefore,

p = q − r + 2 ≥ q − 2q/3 + 2 = q/3 + 2

so p ≥ q/3 + 2. Thus, q ≤ 3p–6.

Intuitively, Theorem 9.2 states that a planar graph of order p cannot have too many edges. We now use an argument similar to the proof of Theorem 9.2 to arrive at our main goal.

Theorem 9.3

Solution of the Three Houses and Three Utilities Problem

The graph K(3, 3) is not planar.

Proof

We prove this result by contradiction. Suppose K(3, 3) is planar. Then we can draw K(3, 3) as a plane graph having r regions. We sum the number of edges lying on the boundary of each region over all r regions of K(3, 3), and denote this number by N. Since no edges join vertices within each vertex subset of K(3, 3), the graph contains no triangles, so it follows that N ≥ 4r. On the other hand, N counts each edge at most twice, so N ≤ 2q = 18. Therefore,

4r ≤ 18 or r ≤ 9/2.

However, by Theorem 9.1, p − q + r = 2, so

6 − 9 + r = 2 2 or r = 5.

This produces the desired contradiction. ▋

We can now see that it is impossible to connect each utility with each of the three houses without lines or mains crossing.

As an application of Theorem 9.2, we show that the complete graph K₅ is not planar.

Theorem 9.4

The graph K₅ is not planar.

Proof

The graph K₅ has p = 5 and

q = p(p − 1)/2 = 10.

Since 3p − 6 = 9, we have q > 3p − 6. Therefore, by Theorem 9.2, K₅ is not planar. ▋

The nonplanar graphs K₅ and K(3, 3) play a major role in the theory of planar graphs. We discuss this briefly.

By a subdivision of a graph G, we mean a graph obtained from G by inserting vertices (of degree two) into the edges of G. For the graph G of Figure 9.5, the graph H is a subdivision of G, while F is not a subdivision of G.

Figure 9.5

We can now state a well-known theorem from graph theory. However, the proof is too complicated to present here.

Theorem 9.5

A graph G is planar if and only if G contains no subgraph isomorphic to K₅ or K(3, 3) or any subdivision of K₅ or K(3, 3).

Although we introduced planar graphs by means of a problem which might be of interest, the problem is not considered to be of any real importance. However, planar graphs are intimately associated with printed electronic circuits, where vertices represent terminals and an edge joins two vertices if a conducting path connects the two corresponding terminals. We do not wish two paths to cross, for this would create a short circuit.

Problem Set 9.1

1. Draw the graphs K(2, 3), K(2, 4), K(2, 5), and K(4, 4).

2. Show that the graphs G₁ and G₂ of Figure 9.6 are planar.

Figure 9.6

3. For the plane graph G of Figure 9.7, determine the vertices and edges of the boundary of region R and the boundary of the exterior region.

Figure 9.7

4. Determine plane graphs G′₁ and G′₂ isomorphic to G₁ and G₂, respectively, of Figure 9.6. Use Theorem 9.1 to determine the number of regions of G′₁ and G′₂.

5. Let G be a connected planar graph. Show that no matter how G is drawn as a plane graph, it always has the same number of regions.

6. Figure 9.8 shows a tetrahedron and a cube. These are examples of polyhedra, which are geometric solids whose faces are all identical. Let V denote the number of vertices of a polyhedron, and let E and F denote the number of edges and number of faces, respectively. Determine V − E + F for the tetrahedron and the cube. Compare this with Theorem 9.1.

Figure 9.8

7.

Give an example of a connected (p, q) planar graph such that equality holds in Theorem 9.2.

Give an example of a connected (p, q) planar graph such that the strict inequality holds in Theorem 9.2.

*8. Show that Theorem 9.2 is true even if G is disconnected.

*9. True or false? If G is a connected (p, q) graph and q = 3p − 6, then G is planar. Explain.

10. Suppose the Three Houses and Three Utilities Problem were the Five Houses and Two Utilities Problem. What would the solution be? What if it were the n Houses and Two Utilities Problem? What if it were the n Houses and Three Utilities Problem?

11. Which complete graphs are planar?

12. Show that K(2, 2) is a subdivision of K₃.

*13. Figure 9.9 shows a famous graph called the Petersen graph. Is the Petersen graph planar? (Hint: Try to make use of Theorem 9.5.)

Figure 9.9

9.2 A Scheduling Problem: An Introduction to Chromatic Numbers

The Scheduling Problem

SUPPOSE YOU ARE A department chairman at a college, and one of your responsibilities is to set up the schedule of courses offered for the next semester. If the college is not too large, it might very well be practical to have the students indicate which courses they plan to take. As you set up the schedule, you must, of course, be careful not to have two courses meet at the same time if a student plans to take both courses. On the other hand, it is most convenient to set up a schedule requiring the fewest number of time periods during the day, since then it might be possible to eliminate classes meeting at unpopular times (such as the time this class meets). The question is: What is the minimum number of hours needed for such a schedule?

We first show how this problem is related to graphs. We construct a graph G₀ by associating a vertex of G₀ with each class in the schedule. We join two vertices of G₀ by an edge if and only if some student is a member of both corresponding classes. We now interrupt our consideration of the graph G₀ to introduce a new graph theoretic concept. We shall soon show a relationship between the two ideas.

By a coloring of a graph G, we mean the assignment of colors (which are simply the elements of some set) to the vertices of G, one color to each vertex, so that adjacent vertices are assigned different colors. An n-coloring of G is a coloring of G using n colors. Figure 9.10 shows a 5-coloring of the graph G₁ where the colors are denoted by numbers, as well as a 4-coloring of the graph G₂.

Figure 9.10

Observe that it is always possible to give a p-coloring to a graph G of order p. It is a more interesting (and more challenging) problem to determine those numbers n, where n < p, for which an n-coloring of G exists. Both a 4-coloring and a 3-coloring exist for the graph G₁ of Figure 9.10; however, there is no n-coloring, where n < 4, for the graph G₂ of Figure 9.10.

We now introduce the main concept of this section. The chromatic number of a graph G is the minimum value n for which an n-coloring of G exists. The chromatic number of G is denoted χ(G) (“χ” is the Greek letter chi). Thus, for the graphs of Figure 9.10 we have χ(G₁) = 3 and χ(G₂) = 4. Note that although we have stated the chromatic numbers of these two graphs, we have not given any verification of these facts.

We now prove that χ(H) = 4 for the graph H of Figure 9.11. First, it is clear that χ(H) ≤ 4 since Figure 9.11(a) gives a 4-coloring of H. It will follow that χ(H) = 4 if we can show there is no 3-coloring of H. Suppose there is a 3-coloring of H, and denote the colors by 1, 2, and 3. Suppose the vertices of H are labeled as in Figure 9.11(b).

Figure 9.11

Now the vertices v₁, v₂, and v₃ form a triangle; therefore, three colors are required to color these vertices. Without loss of generality, we assign color 1 to v₁, color 2 to v₂, and color 3 to v₃. Since v₄ is adjacent to both v₂ and v₃, we must assign color 1 to v₄. (Recall that we are assuming only colors 1, 2, and 3 are necessary.) By the same reasoning, we must assign the color 3 to v₅. However, now v₆ is adjacent to a vertex colored 1, a vertex colored 2, and a vertex colored 3. This gives us a contradiction. Hence, there exists no 3-coloring of H.

We now return to our scheduling problem and the resulting graph G₀.

Theorem 9.6

The minimum number of hours required for the schedule of classes in our scheduling problem is χ(G₀).

Proof

Suppose χ(G₀) = m, and suppose the colors used in coloring G₀ are 1, 2,..., m. We first claim that all classes can be scheduled in m one-hour time periods. In order to see this, consider all those vertices colored 1, say, and the classes corresponding to these vertices. Since no two vertices colored 1 are adjacent, no two classes corresponding to such vertices contain the same student. Hence, all these classes can be scheduled to meet at the same time. That is, all classes corresponding to same-colored vertices can meet at the same time. Therefore, all classes can be scheduled to meet during m time periods.

Now we show that all classes cannot be scheduled in less than m hours. We prove this by contradiction. Suppose we can schedule the classes in k one-hour time periods, where k < m. We can then k-color the graph G₀ by coloring with the same color all vertices which correspond to classes meeting at the same time. To see that this is a legitimate k-coloring of Go, consider two adjacent vertices. These vertices correspond to two classes containing one or more common students. Hence, these classes meet at different times, and thus the two vertices are colored differently. However, a k-coloring of G₀ produces a contradiction, since χ(G₀) = m. ▋

Theorem 9.6 would completely solve our scheduling problem except for one unfortunate fact: ordinarily, it is extremely difficult to determine the chromatic number of a graph. There is no known formula that gives the chromatic number of a graph. However, we present the following result related to chromatic numbers. We write A(G) to denote the maximum degree among the vertices of G.

Theorem 9.7

For any graph G,

χ(G) ≤ 1 + Δ(G).

Proof

We prove the result by induction on the order p of the graph. There is only one graph with p = 1, namely K₁. Since χ(K₁) = 1 and Δ(G) = 0,

χ(K₁) ≤ 1 + Δ(K₁) = 1 + 0

so the result is true for p = 1.

Assume the result is true for all graphs with p = k − 1 vertices, and let G be a graph with p = k vertices. We show that there exists a (1 + Δ(G))-coloring of G, implying that χ(G) ≤ 1 + Δ(G). Let v be a vertex of G and consider the graph G − v. Since G − v has k − 1 vertices, it follows by the induction hypothesis that χ(G − v) < 1 + Δ(G − v). Hence there exists a (1 + Δ(G − v))-coloring of G − v. Let such a coloring of G − v be given. Now there are at most Δ(G) vertices adjacent to v in G, so no more than Δ(G) colors are used in coloring these vertices in G − v. If Δ(G − v) = Δ(G), then some color used in coloring G − v is available for v, and we have a (1 + Δ(G))-coloring of G. If Δ(G − v) < Δ(G), then we may introduce a new color for v, obtaining a coloring of G that requires no more than 1 + Δ(G) colors. In any case, χ(G) ≤ 1 + Δ(G). ▋

Applying Theorem 9.7 to the graph H of Figure 9.11, we have χ(H) ≤ 1 + Δ(H) = 6. However, we have already seen that χ(H) = 4.

Problem Set 9.2

14. What is the chromatic number of Kp?

15. What is the chromatic number of a cycle?

16. What is the chromatic number of a tree?

17. What does Theorem 9.7 indicate about the chromatic number of K(3, 3)? K(4, 4)? K(n, n)? What is the chromatic number of K(3, 3)? K(4, 4)? K(n, n)?

*18. What can you say about the chromatic number of a bipartite graph? What do you think a natural definition of “tripartite graph” is? What can you say about the chromatic number of a tripartite graph?

*19. Prove that χ(G₁) = 3 for the graph G₁ of Figure 9.10.

*20. Prove that χ(G₂) = 4 for the graph G₂ of Figure 9.10.

21. A mathematics department chairman plans to offer seven graduate courses next semester, namely combinatorics (C), group theory (G), linear programming (L), numerical analysis (N), probability (P), statistics (S), and topology (T). The mathematics graduate students and the courses they plan to take are:

Android: C, L, T
Bob: C, G, S
Carol: G, N
Don: C, L
Ed: L, N
Fred: C, G
Ginny: N, P
Homer: G, L
Inga: C, T
Janet: C, S, T
Ken: P, S
Linda: P, T

How many time periods are needed for these seven courses?

*22. Let U = {1, 2, 3,..., 10}. Furthermore, consider the following subsets of U:

A₁ = {1, 2, 6, 9}
A₂ = {2, 7, 8}
A₃ = {4,6,10}
A₄ = {3, 5, 8}
A₅ = {6, 7, 9}
A₆= {1, 2, 3, 4, 6}
A₇ = {8, 9}
A₈ = {1, 2, 6, 10}
A₉ = {1, 3, 4, 5, 9}
A₁₀ = {1, 2, 3, 7}
A₁₁ = {2, 4, 6, 7}
A₁₂ = {1, 3, 5}
A₁₃ = {2, 4, 6, 10}
A₁₄ = {5, 8}
A₁₅ = {7, 8, 9}

Determine the minimum number n such that S₁, S₂,...,Sn are collections of the given subsets of U with the properties that each subset of U belongs to exactly one Si, 1 ≤ i ≤ n, and every two subsets of U belonging to the same Si are disjoint.

9.3 The Four Color Problem

In the first two sections of this chapter we discussed planar graphs and chromatic numbers. In this section we mention a problem involving both concepts, and which is one of the most famous problems in all mathematics.

The Four Color Problem

TO DESCRIBE THIS PROBLEM, we begin with a map, divided into countries, say. We then assign a color to each country so that adjacent countries (i.e., countries sharing some common boundary) are assigned different colors. What is the least number of colors required to color all countries in the map? Of course, the answer depends on the countries and their geographic relationship to each other. Many mathematicians thought that no map, no matter how complicated, would require more than four colors. Whether this is true or not became known as the Four Color Problem.

This famous problem originated in 1852, and was finally solved in 1976 when Appel and Haken showed it was true indeed that every map could be colored with four or fewer colors. It might seem that this should have ended interest in the Four Color Problem; however, such was not the case, due to the unusual nature of the solution. Appel and Haken solved the Four Color Problem by dividing the problem into nearly two thousand cases, according to the arrangements of countries within a map. To determine the possible ways of assigning colors in the various arrangements, they wrote computer programs to analyze the various colorings in each arrangement. After 1200 hours of computer calculations, they declared the problem solved!

Even though the solution of the Four Color Problem must be classified as a monumental achievement, many mathematicians were dissatisfied with (and some even skeptical of) the proof. Thus, a new problem arose; namely, does there exist a purely mathematical proof, unaided by computers, showing that every map can be colored with four or fewer colors? It is quite likely that no solution to this problem will be found during your lifetime (particularly if you are old).

Figure 9.12

The Four Color Problem is closely related to graph theory. With each map we can associate a graph G whose vertices correspond to the countries, and where two vertices are adjacent if the corresponding countries are adjacent. Necessarily, each such graph G is a planar graph. Figure 9.12 shows a map and the corresponding planar graph H. We have already seen that χ(H) = 4. Since every map can be colored with at most four colors, we have the following theorem.

The Four Color Theorem

If G is a planar graph, then χ(G) ≤ 4.

Despite the fact that it is extraordinarily difficult to prove the Four Color Theorem, it is, surprisingly, not particularly difficult to prove the Five Color Theorem. To prove this theorem, the following result is useful.

Theorem 9.8

Every planar graph G contains a vertex v such that deg v ≤ 5.

Proof

The result is obvious if G has six or fewer vertices. Suppose G is a (p, q) graph, where p ≥ 7. If we sum the degrees of the vertices of G, we obtain 2q. If every vertex has degree 6 or greater, then the sum of the degrees of the vertices of G is at least 6p, i.e., 2q ≥ 6p. On the other hand, by Theorem 9.2 we have q ≤ 3p − 6, so 2q ≤ 6p − 12. This is a contradiction. Therefore, not all vertices can have degree 6 or more, and so there exists a vertex v for which deg v ≤ 5.

Theorem 9.9

The Five Color Theorem

If G is a planar graph, then χ(G) ≤ 5.

Proof

The proof is by induction on the order p of the graph. For p = 1, the result is obvious.

Assume that all planar graphs with p = k − 1 have chromatic number at most 5, and let G be a planar graph of order k. By Theorem 9.8, G contains a vertex v such that deg v ≤ 5. Let us draw G as a plane graph, and consider the plane graph G − v. Since G − v has order k − 1, it follows by the induction hypothesis that χ(G − v) ≤ 5. This means we can perform a 5-coloring of G − v. We now assume that we have a 5-coloring of G − v, denoting the colors by 1, 2, 3, 4, and 5. If one of these colors is not used in coloring the vertices adjacent with v, then we may assign that color to v, producing a 5-coloring of G. Hence, we may assume that deg v = 5 and all five colors are used for the vertices adjacent with v.

Suppose v₁, v₂, v₃, v₄, v₅ are the five vertices adjacent with v, arranged cyclically about v, and suppose v₁ has been colored 1, v₂ has been colored 2, etc. We now show that it is possible to recolor certain vertices of G − v, including a vertex adjacent with v, so a color becomes available for v. Consider the colors 1 and 3, and all the vertices of G − v which have been colored 1 or 3. Of course, v₁ is colored 1 and v₃ is colored 3. In G − v there may or may not be a v₁−v₃ path whose vertices are all colored 1 or 3 (see Figure 9.13). First we assume there is no such path. We consider all paths starting at v₁ whose vertices are all colored 1 or 3. These paths produce a subgraph of G − v, which we denote by H. Necessarily, v₃ is not in H; in fact, no vertex adjacent to v₃ is in H.

Figure 9.13

Now we interchange the colors of the vertices of H, producing another 5-coloring of G − v. However, this 5-coloring of G − v assigns the color 3 to both v₁ and v₃. Thus, we may now assign the color 1 to vertex v, producing a 5-coloring of G. Therefore χ(G) ≤ 5.

Suppose, then, there does exist a v₁−v₃ path P in G − v, whose vertices are all colored 1 or 3. (If we interchanged the colors I and 3 of the vertices of H in this case, v₁ would be colored 3 and v₃ would be colored 1, and no color would be available for v. So we proceed in a different manner.) The path P together with the path v₃, v, v₁ produces a cycle in G which either encloses v₂ or encloses v₄ and v₅. Hence there does not exist a v₂ − v₄ path in G − v whose vertices are all colored 2 or 4. As before, we consider all paths beginning at v₂ whose vertices are colored 2 or 4. These paths produce a subgraph of G − v which we represent by F. We interchange the colors of the vertices in F, producing a new 5-coloring of G − v in which both v₂ and v₄ are colored 4. Hence, we may assign the color 2 to v, giving us a 5-coloring of G. Thus, χ(G) ≤ 5. ▋

Problem Set 9.3

23. What is the smallest order of a planar graph G for which χ(G) = 4?

*24. Show that every planar graph of order at least two contains at least two vertices whose degrees are five or less.

*25. Show that it is impossible to improve Theorem 9.8 by replacing “5” by ”4” in its statement; that is, show there exists a planar graph whose every vertex has degree 5 or more.

26. Show that χ(K₅) = 5. Does this contradict the Four Color Theorem? Explain.

27. Does there exist a nonplanar graph with chromatic number one? two? three?

Suggestions for Further Reading

A great deal has been written about planar graphs. For the reader who wishes to learn more about the subject, the article by Harary [2] is a good place to begin.

The Four Color Problem has fascinated the mathematical world for well over a century. An interesting historical account of this problem prior to its solution was written by May [4]. Two other informative articles on the Four Color Problem are due to Harary [3] and Saaty [5]. A description of the proof of the Four Color Theorem by Appel and Haken may be found in [1].

W. Haken, “An attempt to understand the Four Color Problem.” Journal of Graph Theory, 1 (1977), pp. 193–206.

F. Harary, “Recent results in topological graph theory.” Acta Mathematica Academiae Scientiarum Hungaricae, 15 (1964), pp. 405–412.

F. Harary, “The four color conjecture and other graphical diseases.” Proof Techniques in Graph Theory. Academic Press, New York (1969), pp. 1–9.

K. O. May, “The origin of the four-color conjecture.” Isis, 56 (1965), pp. 346–348.

T. L. Saaty, “Thirteen colorful variations on Guthrie’s four-color conjecture.” American Mathematical Monthly, 79 (1972), pp. 2–43.

*Chapter 10

Graphs and Other Mathematics

Graph theory has close relationships with several mathematical areas. In this chapter we consider three of these areas: matrices, topology, and groups.

10.1 Graphs and Matrices

A graph is completely determined by its vertex set and by a knowledge of which pairs of vertices are adjacent. This same information can easily be given by a matrix. In fact, much of graph theory could be investigated as a subject within matrix theory. There are certain advantages to this approach, since matrices can serve as computer input to work a variety of computations. On the other hand, there are several disadvantages to representing graphs as matrices, for this destroys the visual aspect of graphs, and the recognition of certain graphical properties in matrices is not necessarily simpler than in the diagram of a graph.

Let G be a graph of order p with vertices denoted by v₁, v₂,..., vp. Then the adjacency matrix A = A(G) = [aij] is that p x p matrix in which aij = 1 if vi and vj are adjacent and aij = 0 otherwise. Thus, the matrix A is a (0, 1) matrix (i.e., every entry of A is 0 or 1); the main diagonal of A consists entirely of 0’s (i.e., aii = 0 for i = 1, 2, ..., p); and A is symmetric (i.e., aij = aji for 1 ≤ i ≤ p and 1 ≤ j ≤ p). A graph G and its adjacency matrix are given in Figure 10.1.

Figure 10.1

Note that the adjacency matrix of a graph G ordinarily depends on how we label the vertices. For example, the graph G of Figure 10.1 is shown again in Figure 10.2 with a different labeling, resulting in a different adjacency matrix. Although the matrices of Figures 10.1 and 10.2 are unequal (as matrices), they represent isomorphic graphs.

Figure 10.2

One interesting property of an adjacency matrix of a graph concerns the entries of its various powers. The length of a walk is the number of occurrences of edges in it, and two u−v walks of the same length are equal if their edges occur in exactly the same order.

Theorem 10.1

Let A be the adjacency matrix of a graph G, where V(G) = {v₁, v₂, ..., vp}. Then the (i, j) entry of An, n ≥ 1, is the number of different vi−vj walks of length n in G.

Proof

The proof is by induction on n. For n = 1, we are considering the adjacency matrix A itself. The graph G contains a vi−vj walk of length one if and only if v¡vj is an edge of G. If the (i, j) entry is 1, then v¡vj is an edge of G; if the (i,j) entry is 0, then vivj is not an edge of G. Therefore, the result is true for n = 1.

Let An−1 = [aij(n−1)], n ≥ 2; that is, denote the (i, j) entry of the (n − 1)st power of A by aij(n−1). Assume aij(n−1) is the number of different vi−vj walks of length n − 1 in G. We now consider An, where, say, An = [aij(n)]. Since An = An−1 A, we can use the definition of matrix multiplication to obtain

Every v¡−vj walk of length n in G consists of a vi−vk walk of length n − 1, where vk is adjacent to vj, followed by the edge vk vj and the vertex vj. Thus, aij(n) counts the number of different vi−vj walks of length n in G. ▋

Figure 10.3

As an illustration of Theorem 10.1, we again turn to the graph G of Figure 10.1 and its adjacency matrix A. We compute A² and A³ as in Figure 10.3. The (1, 2) entry of A³ in Figure 10.3 is 3; hence, there are three v₁−v₂ walks of length 3 in G, namely

W₁ : v₁, v₂, v₃, v₂; W₂ : v₁, v₂, v₄, v₂ ;

W₃ : v₁, v₂, v₁, v₂.

We now consider a second matrix which can be associated with a graph. Let G be a graph of order p and size q such that V(G) = {v₁, v₂, ..., vp} and E(G) = {e₁, e₂, ..., eq}. The incidence matrix B = B(G) = [bij] is that p x q matrix in which bij = 1 if vi is incident with ej, and bij = 0 otherwise. As with the adjacency matrix, the incidence matrix is a (0, 1) matrix. However, in general, the incidence matrix is not symmetric; in fact, in general, it is not a square matrix.

The particular incidence matrix obtained depends on how we label both vertices and edges. Figure 10.4 gives an example.

Figure 10.4

Problem Set 10.1

1. Label the vertices of the graph G = K(2, 3) and determine the adjacency matrix A = A(G). Compute the matrix A² and interpret its entries, using Theorem 10.1.

2. Let G = K(n, n), n ≥ 2. Furthermore, let V(G) = V₁ ∪ V₂, where V₁ = {v₁, v₂,...,vn} and V₂ = {vn+1, vn+2,..., v2n}, and v¡vj ∈ E(G) if and only if v¡ ∈ V₁ and vj ∈ V₂. Determine the adjacency matrix A = A(G). Then, without performing any matrix multiplication, determine A² and A³.

3. We pointed out that if A is the adjacency matrix of a graph G of order p, then A is a p × p, (0, 1), symmetric matrix with 0’s along the main diagonal. Show that these properties are sufficient to characterize adjacency matrices; that is, if A is a p x p, (0, 1), symmetric matrix with 0’s along the main diagonal, then A is the adjacency matrix of some graph G.

4. Determine the adjacency matrix A of the graph G of Figure 10.4. Without performing any matrix multiplication, determine A² and A³.

5. If A is the adjacency matrix of a graph G and A² = [aij⁽²⁾], describe aij⁽²⁾, i ≠ j, and aii⁽²⁾ without using the word “walk.”

6. Label the edges of the graph G of Figure 10.1 and then determine the incidence matrix of G.

7. Show that if the incidence matrix of a graph G is a square matrix, then G contains a cycle.

8. Characterize those matrices which are incidence matrices of graphs.

9. Let Mt denote the transpose of a matrix M, i.e., the first row of Mt is the first column of M, the second row of Mt is the second column of M, etc. For the graph G of Figure 10.4, compute the product B · Bt. If B is the incidence matrix of a graph G, try to describe what you can expect, in general, for the product B · Bt.

10. Define another matrix which can be associated with a graph.

10.2 Graphs and Topology

Some aspects of graph theory are very closely tied to the mathematical field of topology, particularly that topic called “surface topology.” Actually, we discussed relationships between graphs and surfaces in Chapter 9 when we considered planar graphs and the Four Color Problem.

As we already noted, we can draw only certain graphs in the plane so that no edges intersect except at vertices; these are called planar graphs. Such a “drawing” is also called an embedding of the graph in the plane. It is not too difficult to see that planar graphs are precisely those graphs which can be embedded on the surface of a sphere. For example, Figure 10.5 shows the graph K₄ embedded on a sphere. Hence, “spherical graphs” and planar graphs are exactly the same. Of course, every graph can be embedded in 3-dimensional space.

Figure 10.5

Another kind of surface that plays an important role in topology is the doughnut-shaped surface called the torus. Figure 10.6 shows the graph K₄ embedded on a torus. If G is a graph embedded on the torus, then the regions of G are the connected pieces of the torus remaining after we remove the vertices and edges of G. (Recall the definition of “region” in the case of plane graphs.) In the case of the graph K₄ embedded on the torus in Figure 10.6, there are four regions.

Figure 10.6

By definition, all regions are connected, whether they are determined from graphs embedded on the sphere or on the torus. However, a region may also have another important property. A region is called simply connected if any simple closed curve (such as a circle or ellipse) can be “continuously deformed” (i.e., shrunk or contracted) in that region to a single point. For example, in Figure 10.6 the region R is not simply connected, for if we consider the simple closed curve C shown in region R, then C cannot be continuously deformed in R to a single point. All three other regions of K₄ in Figure 10.6 are simply connected.

If a connected (planar) graph is embedded on the sphere, then every region is necessarily simply connected. However, this need not be the case for connected graphs embedded on the torus. A graph is called toroidal if it can be embedded on the torus. Every planar graph is toroidal; however, the converse statement is false, i.e., there are nonplanar graphs which can be embedded on the torus. One such example is K₅, shown embedded on the torus in Figure 10.7.

Figure 10.7

Another way of drawing graphs on the torus often proves convenient. First we consider how to construct the torus. We begin with a rectangle, and then we bend it in the shape of a cylinder so that the top and bottom sides meet. We then bend it again so that the two ends meet, thereby obtaining a torus. Figure 10.8 illustrates this process.

Figure 10.8

Hence, in the original rectangle of Figure 10.8, opposite sides have been identified with each other. Therefore, the points labeled A in Figure 10.9(a) are the same, as are the points labeled B. This identification of opposite sides is denoted by the arrows going in the same direction. Thus, the graph K₅ can be embedded on the torus, as shown in Figure 10.9(b).

Figure 10.9

In topology, a torus is also known as a sphere with one “handle,” as shown in Figure 10.10. We say that the torus and the sphere with one handle are “topologically equivalent,” or that they are “homeomorphic.”

Figure 10.10

Problem Set 10.2

11. Figure 10.7 shows K₅ embedded on the torus. How many regions are simply connected?

12. Draw the bipartite (nonplanar) graph K(3, 3) on the torus using its rectangular representation. Try to determine the number of regions and how many of these are simply connected.

13. Give an embedding of the nonplanar graph K₆ on the torus.

14. Let G be a connected planar graph. Is the number of regions determined by an embedding of G on the sphere always equal to the number of regions determined by an embedding of G on the torus? Explain.

15. Theorem 9.1 states that if G is a connected graph embedded in the plane and G has p vertices, q edges, and r regions, then the number p − q + r always equals 2. Another theorem states that if G is a connected graph embedded on the torus so that each region is simply connected, and G has p vertices, q edges, and r regions, then p − q + r always equals the same number. Try to determine the value of this number.

16. What do you think a “double torus” is? Give an embedding of K₇ on the double torus. (It turns out that it is possible to embed K₇ even on the single torus, but it is not possible to embed K₈ on the torus.)

17. Show that it is possible to embed a given graph G on a sphere with n handles if we make n large enough.

18. Learn what a Möbius strip is. Explain why every planar graph can be embedded on the Möbius strip and give an embedding of K₅ on the Möbius strip.

10.3 Graphs and Groups

First, let us present (or recall) the definition of a group. By a binary operation ⊗ on a nonempty set Γ, we mean a function associating an element of Γ with each ordered pair (a, b) of (not necessarily distinct) elements of Γ. We denote this element of Γ by a ⊗ b. We emphasize the word “ordered” in the definition, as it need not be the case that a ⊗ b = b ⊗ a.

A group is a nonempty set Γ together with a binary operation ⊗ (usually called multiplication) on Γ satisfying the following three properties:

Associative Law: For any elements a, b, c (not necessarily distinct) of Γ,

a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c.

There exists an element e of Γ (called the identity of Γ) such that

a ⊗ e = e ⊗ a = a

for every element a of Γ.

For each element a of Γ, there exists an element a⁻¹ of Γ (called the inverse of a) such that

a ⊗ a⁻¹ = a⁻¹ ⊗ a = e.

Although groups can take a variety of forms, many important groups arise from permutations (see Section A.4 in the Appendix). We consider some special examples of these groups.

Let G be a graph of order p with vertices labeled v₁, v₂, . . . , vp, say. It is obvious that G is isomorphic to itself; hence there exists an isomorphism α from G to G, i.e., a one-to-one mapping α: V(G) → V(G) which preserves adjacency. In fact, the obvious mapping is α(vi) = vi for i = 1, 2, . . . , p. However, there may well be other mappings (isomorphisms) in addition to this obvious one.

An isomorphism from a graph to itself is called an automorphism of the graph. The set of all automorphisms of a graph G under the binary operation of composition (again refer to Section A.4 of the Appendix) is always a group, called the automorphism group, or simply the group of G, and is denoted by . Before proceeding further, let us consider an illustration.

Example 10.1

Let G be the graph of Figure 10.11, with vertices labeled 1, 2, 3 ; that is, V(G) = { 1, 2, 3}. There are six permutations on V(G); however, only two of these are isomorphisms (automorphisms) of G. The obvious automorphism is

however,

is also an automorphism. Let us consider the composition α₁ ∘ α₀. [Recall that the composition f ∘ g g of functions f and g means that (f ∘ g)(a) = f(g(a)) for each element a on which g is defined.] We see that

(αi ° α₀)(1) = α₁(α₀(1)) = α₁(1) = 3,

(∝₁ ∘ ∝₀) (2) = α₁(α₀(2)) = α₁(2) = 2,

and

(α1 ° α₀)(3) = α₁(α₀(3)) = α₁(3) = 1.

Figure 10.11

Hence,

We also investigate α₁ ∘ α₁. Here we have

(α₁ ∘ α₁)(1) = α₁(α₁(1)) = α₁(3) = 1,

(α₁ ∘ α₁)(2) = α₁(α₁(2)) = α₁(2) = 2,

and

(α₁ ∘ α₁₎(3) = α₁(α₁(3)) = α₁(1) = 3.

Therefore,

For the graph G of Figure 10.11 we have (G) = {α₀, α₁}. Since (G) has two elements, this group has “order” two. The graph G is displayed again in Figure 10.12 together with its group, including the “group table.”

Figure 10.12

With the aid of the group table in Figure 10.12, we can now see that the identity element of (G) is α₀, the inverse of α₀ is α₀, and the inverse of α₁ is α₁.

Example 10.2

Consider the cycle C₄ of Figure 10.13. In addition to the “identity” automorphism

Figure 10.13

there are three automorphisms which might be considered “rotations” of the cycle C₄:

The group (C₄) also contains four other automorphisms which we can interpret as “reflections” of the cycle C₄:

The group (C₄) is summarized in Figure 10.14. We refer to the groups of the cycles Cn as dihedral groups, and denote them by Dn. Hence, Figure 10.14 shows the dihedral group D₄ (of order 8).

(C₄) = D₄ = {α₀, α₁, α₂, α₃, β₁, β2, β₃, β₄}

Figure 10.14

We have seen that we can associate a group with every graph G. We consider the reverse question now of associating a graph with a given group. In this context, we consider only groups of finite order. A group Γ is generated by the elements g₁, g2, . . . , gk (and these elements are called generators) if every element of Γ can be expressed as the product of a finite number of generators and their inverses. A group with one generator is called a cyclic group.

Let Γ be a given finite group with Δ = {g₁, g₂, . . . ., gk} a set of generators for Γ. It is common not to include the identity in a generating set. We describe a graph (actually a digraph) called the Cayley color graph of Γ, denoted by DΔ(Γ). (The symbol “Δ” is included in the notation since the Cayley color graph ordinarily depends on the set of generators chosen. In general, several Cayley color graphs may exist for a given group, depending on the generating set.) We associate a vertex of DΔ(Γ) with each element of group Γ. With each generator gi of Γ we associate a color, say color i. Suppose Γ = {x₁, x₂, . . . , xP} and vertex vi of DΔ(Γ) corresponds to x₁ for i = 1, 2, . . . , p. We draw an arc colored i from v₁ to v₂ if and only if x₂ = x₁gi. This gives us the Cayley color graph of Γ.

Example 10.3

Consider the group Γ = {e, a, b, c, d} with the following group table:

The group Γ is cyclic with generator set Δ = {a} because

a = a, b = a², c = a³, d = a⁴, and e = a⁵.

For convenience we label the vertices of the Cayley color graph DΔ(Γ) in Figure 10.15 with the elements of the group. In this case all arcs of the same color. For example, there is an arc from b to c because c = ba, as can be seen in the group table. Again, other Cayley color graphs can be obtained for Γ = {a, b, c, d, e} by selecting different generating sets, such as Δ’ = {a, b}, for example.

Figure 10.15

Example 10.4

Next we consider the group Γ of all permutations on the set {1, 2, 3}. Here, Γ = {x₁, x₂, x₃, x₄, x₅, x₆), where

The group table in this case is

Here we observe that Δ = {x2’ x₆}, for example, is a generator set for Γ. We associate a solid arc with the color of x₂ and a dashed arc with the color of x₆. This Cayley color graph is shown in Figure 10.16.

Figure 10.16

Problem Set 10.3

19. Determine (K₂).

20. Determine .

21. Determine (K(1, 3)).

22. Determine (K₃).

23. Determine (Pn), where Pn is a path with n ≥ 2 vertices.

24. The dihedral group Dn has order 2n. Describe the 2n automorphisms of Cn, the cycle of order n and size n.

25. Show that for any graph G, the groups (G) and (Ḡ) are the same (isomorphic).

26. Find a generating set Δ for the group Γ = {e, a} with the following group table and draw DΔ(Γ):

27. Find a generating set Δ for the group Γ = {e, a, b} with the following group table and draw DΔ(Γ):

28. Find a generating set Δ for the group Γ = {e, a, b, c} with the following group table and draw DΔ(Γ):

29. Draw DΔ( (K₂)).

30. The graph G = C₄ and (C₄) = (G) are given in Figure 10.14. Find a generating set Δ for the group (G) and draw DΔ((G)).

Suggestions for Further Reading

Harary [3] has written a very readable expository article on graphs and matrices. Furthermore, the books by Harary [2] and Behzad, Chartrand, and Lesniak-Foster [1] each contains a chapter on the subject.

A survey of “topological graph theory” can be found in the article by Kainen [4], while the book by White [5] discusses relationships among “graphs, groups, and surfaces.”

[1] M. Behzad, G. Chartrand, and L. Lesniak-Foster, Graphs & Digraphs. Wadsworth International Group, Belmont, CA (1979).

[2] F. Harary, Graph Theory. Addison-Wesley, Reading, Mass. (1969).

[3] F. Harary, “Graphs and matrices.” SIAM Review, 9 (1967), pp. 83–90.

[4] P. C. Kainen, “Some recent results in topological graph theory.” Graphs and Combinatorics (R. A. Bari and F. Harary, eds.), Springer-Verlag, Berlin (1974), pp. 76–108.

[5] A. T. White, Graphs, Groups, and Surfaces. North-Holland, Amsterdam (1973).

Appendix

Sets, Relations, Functions, and Proofs

Every area of mathematics makes use to some extent of the concepts “set,” “relation,” and “function.” Graph theory not only involves these concepts, but, in fact, “set” and “relation” are fundamental to the meaning of the word “graph” itself. It is therefore essential that we clearly understand these terms. As with every other mathematical subject, the theory of graphs develops through theorems and proofs. We also include a brief discussion of this important topic.

A.1 Sets and Subsets

We give no technical definition of the concept of set, for any attempt to define “set” only uses words whose meaning is synonymous with “set” itself, such as “collection” or “family.” We say that a set is composed of elements, but we will not attempt to define this term either. We will soon clarify how these words are employed.

To describe a set, we list its elements, if this is feasible, or we may present some rule indicating precisely those elements belonging to the set. For example, we may refer to the set of students taking this class. If the number of students is not very large, we can describe this same set by listing the individuals; however, a listing of the students does not suggest what these people have in common, namely that they are all members of this class. Hence we may prefer to describe a set by means of a rule (if possible), independent of the number of elements in the set.

For the most part, we shall use capital (upper case) letters to denote a set, such as U or V, and lower case letters to represent the elements of a set. The notation u ∊ U indicates that u is an element of U, while v₁, v₂ ∊ V implies that v₁ and v₂ are both elements of the set V. If w is not an element of W, we write w ∉ W. To indicate that a set U consists of the elements u₁, u₂ and u3, we write U = {u₁, u2, u₃}. If N denotes the natural numbers (positive integers), then

V = {vi∣1 ≤ i ≤ 100, i ∊ N}

means that V consists of the 100 elements v₁, v₂, etc., up to and including v₁₀₀. More formally, this is read as “the set of all elements vi such that [the vertical bar means ”such that“] 1 ≤ i ≤ 100 and i ∊ N.” Indeed, this same set V could be described equally well by writing

V = {v₁, v₂, . . . , v₁₀₀},

V = {vi∣i = 1, 2, . . . , 100},

or

V = {vi∣1 ≤ i ≤ 100},

since it is understood that i ∊ N.

If U and V are sets with the property that every element of U is an element of V, then we say U is a subsets of V, and write U ⊆ V. If U and V contain precisely the same elements, then U and V are equal sets, denoted U = V. The statement U = V is equivalent to saying U ⊆ V and V ⊆ U.

In accord with the preceding statements,

{u₁, u₂, u₂} = {u₁, U₂} = {u₂, u₁};

that is, the composition of a set is not affected by an element listed more than once, nor by the order in which elements are listed. If U ⊆ V and U ≠ V (that is, U is not equal to V), then every element of U is an element of V, but at least one element of V does not belong to U. Under these conditions, we say U is a proper subset of V, and write U ⊂ V. A set may have no elements; if this is the case, we designate the set by ∅ and call it the null set or empty set. For every set W, it follows that ∅ ⊆ W; for if this were not the case, there would exist an element x such that x ∈ ∅ and x ∉ W. However, this is impossible since ∅ contains no elements.

In any particular discussion concerning sets, the sets involved are usually subsets of some specified set, called the universal set. For example, at a certain time we may be interested in sets of positive integers; in this case, the universal set is N. If U denotes the universal set on some occasion and S is a subset of U, then the complement of S is that set consisting of all elements of U not belonging to S, i.e.,

= {x ∈ U∣x ∉ S}.

Note that U = ∅.

Given two sets V and W, the union of V and W, denoted V ∪ W, is the set consisting of elements belonging to V or W (or both). The intersection V ∩ W of V and W is the set containing those elements belonging to both V and W. If V n W = ∅, then we say V and W are disjoint sets (meaning that V and W have no elements in common). As an illustration, let

U = {u₁, u₂, u₃}, V = {u₁, u₃}, and W = {u₂, u₄}.

Then

U ∪ V = {u₁, u₂, u₃}, U ∩ V = {u₁, u₃},

V ∪ W = {u₁, u₂, u₃, u₄}, U ∩ W = {u₂}, and V ∩ W = ∅.

Therefore, V and W are disjoint.

Two famous set equalities involving complements, unions, and intersections are called DeMorgan’s Laws, stated next. We prove the first of these laws and leave the proof of the second as an exercise.

Theorem A.1

(DeMorgan’s Laws)

Let U be the universal set, and let A and B be subsets of U. Then:

.

Proof of (a)

We give the proof in two parts; specifically, we show .

To prove (i), we let x ∈ . Then x ∈ U but x ∉ A ∪ B. Since x ∉ A ∪ B, the element x belongs to neither A nor B, i.e., x ∉ A and x ∈ B. This implies that x ∈ and x ∈ . Therefore, x ∈∩ . We have thus shown that .

To prove (ii), we let Hence, y ∈ and y ∈ B, so that y ∉ A and y ∉ B. Since y belongs to neither A nor B, it follows that y ∉ A ∪ B, implying that y ∈ . This verifies (ii). ▋

Problem Set A.1

1. How many elements are contained in the set

U ={ui∣1 < i < 10, i ∈ N}?

2. Let U, V, and W be nonempty sets, and suppose that for every element w ∈ W, either w ∈ U or w ∈ V. Show that W ⊆ U ∪ V. (Hint: Let x be any element of W and show that x ∈ U ∪ V.)

3. Let V and W be disjoint sets. Suppose V₁ ⊆ V and W₁ ⊆ W. Show that V₁ and W₁ are disjoint sets. (Hint: Either V₁ and W₁ are disjoint sets or they are not. Suppose they are not. Then there is an element x ∈ V₁ ∩ W₁. Show that this is impossible.)

4. Let V₁ = {v₁, v₃, v₄}, V₂ = {v₂, v₅}, V₃ = {v₁ v₃}, and V₄ = {v₃, v₄}. Determine the union and the intersection of all pairs of these sets. Which sets are disjoint?

5. Let U, V, and W be sets such that U ⊂ V and V ⊆ W. Prove that U ⊂ W.

6. Prove part (b) of Theorem A.1.

A.2 Cartesian Products and Relations

For elements u₁ and u₂ of some set, we write (u₁, u₂) to denote the ordered pair of these two elements. Here, the order in which we write the elements is important; u₁ is the first element and u₂ is the second element. Hence the ordered pair (u2, u₁) is not the same as (u₁, u₂). This differs from the meaning of {u₁, u₂}, where the fact that u₁ is written first has no special significance; that is, {u₁, u₂} = {u₂, u₁}.

The Cartesian product V × W of two sets V and W is the set of all ordered pairs such that the first element of each pair belongs to V and the second element of each pair belongs to W; in symbols,

V x W = {(v, w)∣v ∈ V, w ∈ W}.

If V = {v₁, v₂} and W = {w₁, w₂, w₃}, then

V x W = {(v₁, w₁), (v₁, w₂), (v₁, w₃), (v₂, w₁), (v₂, w₂), (v₂, w₃)}:

also

V × V = {(v₁, v₁), (v₁, v₂), (v₂, v₁), (v₂, v₂)}.

Let ∣S∣denote the number of elements in a set S. (The number ∣S∣is called the cardinality of S.) For a given element v in a set V, the number of ordered pairs in V × W having v as the first element is ∣W∣. Since there are ∣V| different first elements among the ordered pairs being considered, it follows that the total number of ordered pairs in V × W is ∣V∣·∣W∣, i.e.,∣V × W∣ = ∣V∣·∣W∣.

By a relation on a set V, we mean any subset of V × V. Thus, if ∣V∣= n for some finite set V, then a relation on V may have as many as n² elements, or as few as zero elements. For example, suppose V₀ = {a, b, c}. Then one possible relation on V₀ is

R = {(a, b), (b, b), (b, c), (c, b)}.

We say that a is related to b by R because (a, b) ∈ R. However, b is not related to a in this case since (b, a) ∉ R. We can also indicate that (a, b) ∈ R by writing a R b. We can then write b a.

There are several interesting properties of relations on sets. A relation R on a set V is reflexive if for every x ∈ V, the ordered pair (x, x) belongs to R. If V₀ = {a, b, c}, then any reflexive relation on V₀ must include the ordered pairs (a, a), (b, b), and (c, c). A relation R on a set V is irreflexive if for every x ∈ V, it follows that (x, x) ∉ R. We emphasize that if a relation is not reflexive, it need not be irreflexive. For example, if V₁ = {y, z}, then S = {(y, y), (y, z)} is a relation on V₁ which is neither reflexive nor irreflexive.

A relation R on a set V is symmetric if whenever (x, y) ∈ R, then (y, x) ∈ R; the relation is asymmetric if whenever (x, y) ∈ R, where x ≠ y, then (y, x) ∉ R. A relation R on V is called transitive if whenever (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R. Thus, if a relation R on some set V is not symmetric, there exists some ordered pair (a, b) ∈ R, where a ≠ b, such that (b, a) ∉ R. If a relation R is not transitive, then there are ordered pairs (a, b) and (b, c) in R such that (a, c) ∉ R.

Example A.1

Let V = {u, v, w, x} and E = {(u, v), (v, u), (v, w), (w, v)}. Then E is a relation on V which is irreflexive, symmetric, and not transitive.

Example A.2

Suppose V₀ denotes the set of all living people. Let R₁ denote the relation in which (a, b) ∊ R₁ if a, b ∊ V₀ and a is the same age (in years) as b. Then R₁ is reflexive, symmetric, and transitive. Let R₂ denote the relation in which (a, b) ∊ R₂ if a, b ∊ V₀ and a is not the same age as b. If (a, a) ∊ R2, then this implies that the person a is not the same age as himself or herself, which, of course, is impossible. Hence, for every a ∊ V₀, we have (a, a) ∉ R₂, and so R₂ is irreflexive. If (a, b) ∊ R₂, i.e., if a is not the same age as b, then necessarily b is not the same age as a. Therefore, ( b,a) ∊ R₂ and R₂ is symmetric. Finally, suppose (a, b) ∊ R₂ and (b, c) ∊ R₂. Then a is not the same age as b and b is not the same age as c; but we cannot conclude that (a, c) ∊ R₂. For example, a may be 19 years old, b 21 years old, and c 19 years old. In this case, (a, c) ∉ R2. Hence, R₂ is not transitive.

Problem Set A.2

7. Which of the following relations have the properties reflexive, symmetric, transitive on the indicated sets?

“Is parallel to” on the set of lines in the plane.

“Is less than 100 miles from” on the set of cities of the world.

“Is the sister of” on the set of all living people.

8. Let V = {a, b, c, d}, and let R = {(a, a), (a, b), (a, c), (a, d), (b, b), (b, c), (b, d), (c, c), (c, d), (d, d)}. Which properties (reflexive, irreflexive, symmetric, asymmetric, transitive) does the relation R possess?

9. Let V = {a, b, c, d}. Give an example of a relation on V which is not reflexive, symmetric, or transitive.

10. Let V = {a, b, c, d}. Determine a reflexive, symmetric, transitive relation on V containing (a, b), (b, c), and (c, d). Show that there is only one relation having these properties.

11. Let V be a nonempty set, and let R = ∅ be the “empty” relation on V. Does R have any of the reflexive, symmetric, and transitive properties?

12. Let V = {a, b, c}. Give an example of a relation on V which is:

reflexive and symmetric, but not transitive.

reflexive and transitive, but not symmetric.

symmetric and transitive, but not reflexive.

A.3 Equivalence Relations

Relations which are reflexive, symmetric, and transitive are called equivalence relations and play an important role in all branches of mathematics. More formally, a relation R on a set A is called an equivalence relation if the following three properties are satisfied:

(i) a R a for all a ∊ A;

(ii) a R b implies b R a for all a, b ∊ A ;

(iii) a R b and b R c implies a R c for all a, b, c ∊ A.

Examples of equivalence relations are numerous. Rather than presenting examples dealing with abstract sets, we illustrate equivalence relations on sets which we can describe in a less abstract manner. All of the following relations are equivalence relations on the indicated sets:

“Is equal to” on the set of integers. (This follows since a = a for every integer a; if a = b then b = a; and if a = b and b = c, then a = c.)

“When divided by the positive integer m, has the same remainder as” on the set of integers.

“Is parallel to or coincides with ” on the set of lines in the plane.

“Is congruent to” on the set of triangles in the plane.

“Has the same first name as” on the set of all people with first names.

“Has the same number of pages as” on the set of all books.

One of the most important properties of equivalence relations deals with what are called “partitions” of sets. We now consider this property.

Let R be an equivalence relation on a set A. Then for a ∊ A, we define the subset [a] as follows:

[a] = {xlx∊A,xR a}.

The sets [a], a ∊ A, are called equivalence sets or equivalence classes. Since R is an equivalence relation, R is reflexive, and therefore a ∊ [a].

If A1, A₂, ..., An are nonempty, pairwise disjoint subsets (i.e., every two subsets are disjoint) of a nonempty set A such that the union of all subsets is A, then the set {A₁, A₂, . . . , An} of these subsets is called a partition of A. With these definitions in mind, we can now present the result we are interested in.

Theorem A.2

Let R be an equivalence relation on a nonempty set A. Then the set S = {[a]| a ∈ A} of equivalence classes is a partition of the set A.

Proof

We must show that the set of equivalence classes satisfies the definition of a partition of A. First we observe that if [c] is an equivalence class, say, then [c] is nonempty since c ∈ [c]. Furthermore, for an arbitrary element b ∊ A, we have b ∈ [b]; therefore, the union of the elements of S is A.

It remains for us to show that every two distinct elements of S are disjoint. Suppose [b] and [c] are two distinct elements of S. We shall assume [b] and [c] are not disjoint; then, under this assumption, we shall prove [b] = [c]. This, however, contradicts the fact that [b] and [c] are distinct, implying that our assumption that [b] and [c] are not disjoint is incorrect. Therefore, [b] and [c] are disjoint.

Since we are assuming [b] and [c] are not disjoint, it follows that [b] ∩ [c] ≠ ∅. This implies that there exists an element x ∊ A such that x ∈ [b] n [c]; hence, x ∈ [b] and x ∈ [c]. Thus, x R b and x R c. Since R is symmetric, b R x, and since R is transitive, b R c (so that c R b).

We now show that [b] = [c]. We do this by verifying that each of [b] and [c] is a subset of the other. Suppose y is any element of [b], so y R b. Because b R c and R is transitive, we conclude that y R c and y ∈ [c]; that is, any element of [b] is also an element of [c]. Therefore, [b] ⊆ [c]. Now suppose z ∈ [c], so z R c. Since c R b, we have z R b and z ∈ [b]. Thus, [c] ⊆ [b], thereby proving [b] = [c]. This gives us the desired contradiction and completes the proof that the elements of S give a partition of A. ▋

Let us illustrate Theorem A.2. Let A = {1, 2. 3, 4, 5, 6} and let R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5), (6, 6)}. We can show that R is an equivalence relation on A. Hence, by Theorem A.2, {[a] ∣a E A} is a partition of A. In this case, the choices for a are 1, 2, 3, 4, 5, and 6. We have [1] = {1, 2, 3}, [2] = {1, 2, 3}, [3] = {1, 2, 3}, [4] = {4, 5}, [5] = {4, 5} and [6] = {6}. Hence

{[a]∣a ∈ A} = {[1], [2], [3], [4], [5], [6]} = {[1]> [4], [6]),

the last equality following because [1] = [2] = [3] and [4] = [5]. We now observe that {[1], [4], [6]} is indeed a partition of A. This is shown pictorially in Figure A.1, where we see how the set A is partitioned by the equivalence relation R.

Figure A.1

We give one final (but important) example of an equivalence relation. Let Z denote the set of integers, and let m, d ∊ Z, where d ≠ 0. We say d divides m, written d∣m, if an integer q exists such that m = dq. Next, let a, b, n ∊ Z, where n ≥ 2. We say a is congruent to b modulo n if n (a − b), and write a ≡ b (mod n).

Theorem A.3

Let n (≥2) be an integer. The relation “is congruent to modulo n” is an equivalence relation on Z.

Proof

Let a ∈ Z. Then n |(a − a) since a − a = n · 0. Therefore, a ≡ a (mod n) for every a ∈ Z and the relation is reflexive.

Let a, b ∈ Z and suppose a ≡ b (mod n). Hence n ∣(a − b), which implies that an integer q exists such that a − b = nq. Thus, b − a = n(−q). Since −q ∈ Z, it follows that n |(b − a), so b ≡ a (mod n) and the relation is symmetric.

Let a, b, c ∈ Z and suppose a ≡ b (mod n) and b ≡ c (mod n). Thus, n∣(a − b) and n∣(b − c). This implies that there exist integers q₁ and q₂ such that a − b = nq₁ and b − c = nq₂. Adding these two equalities, we obtain

a − c = nq₁ + nq₂ = n(q₁ + q₂).

Since q₁ + q₂ ∊ Z, we conclude that n|(a − c), so that a ≡ c (mod n) and the relation is transitive. ▋

The set of distinct equivalence classes resulting from the equivalence relation of Theorem A.3 is referred to as the integers modulo n and is denoted by Zn or Z/(n). For example, if n = 5, then Z₅ = {[0], [1], [2], [3], [4]}, where and

Problem Set A.3

13. Let A denote the set of all people, and let R denote the relation “is born in the same year as” on the set A. Show that R is an equivalence relation on A. Describe the elements of the set {[a]∣a∊A}.

14. Let A = {1, 2, 3, 4, 5, 6} and suppose R is an equivalence relation on A. If 1 R 3, 3 R 4, 2 R 6, and ∣{[a]|a ∊ A}| = 3, determine the elements of R. Also, determine the distinct equivalence classes in this case.

15. Let A be a nonempty set, and let R be a relation on A with the property that a R b for any elements a and b in A (a and b need not be distinct). Show that R is an equivalence relation on A. Determine the equivalence classes.

16. Let A be a nonempty set, and let S = {A₁, A₂, ... , An} be a set of subsets of A forming a partition of A. Determine an equivalence relation R on A such that the set {[a]| a ∊ A} is precisely the set S.

17. Describe the contents of the distinct elements of Z₂ and Z₃.

18. How many distinct elements are in Zn, where n ≥ 2? Describe the set Zn.

19. Let R be a relation defined on Z by a R b if a + b ≡ 0 (mod 2). Show that R is an equivalence relation and determine the distinct equivalence classes.

20. Let R be a relation defined on Z by a R b if a +b ≡ 0 (mod 3). Show that R is not an equivalence relation.

21. Let R be a relation defined on Z by a R b if a² ≡ b² (mod 5). Show that R is an equivalence relation and determine the distinct equivalence classes.

A.4 Functions

Let A and B be two nonempty sets. Then a function f from A to B (denoted f : A → B) is a set of ordered pairs (a, b), with a ∈ A and b ∈ B, satisfying the property that for every element a ∈ A there exists exactly one ordered pair in f containing a as the first element of the pair. For example, let A denote the set of all circles and let B denote the set of real numbers. We can define a function f₁ : A → B by letting (a, b) ∈ f₁ provided a is a circle and b is the area of a. With the same two sets A and B, we can define another function ƒ₂ : A → B by letting (a, b) ∈ f₂ provided a is a circle and b is the circumference of a. Hence, the function ƒ₁ associates an area with a circle and f₂ associates a circumference with a circle.

Let A = {a, b, c} and B = { 1, 2, 3, 4}. Then g₁ = {(a, 2), (b, 4)} and g₂ = {(a, 3), (b, 1), (c, 2), (c, 4)} are not functions from A to B, while g₃ = [(a, 4), (b, 4), (c, 2)} is a function from A to B. Note that if A is a nonempty finite set with, say, n elements and B is any nonempty set, then every function ƒ : A → B has exactly n ordered pairs.

If f : A → B is a function from A to B, then it is also customary to call f a mapping from A to B and say that f maps A into B. Furthermore, if (a, b) f then we can write b = f(a) and say a is mapped into b by f and b is the image of a under f. According to the definition of “function,” every element of A has exactly one image; on the other hand, an element of B may be the image of one, several, or no elements of A.

If a function f : A → B has the property that every element of B is the image of at least one element of A, then we say ƒ is a mapping from A onto B. If A = {a, b, c} and B = {1, 2, 3}, then ƒ = {(a, 2), (b, 1), (c, 1)} is a function from A into B, but f is not a function from A onto B since 3 is not the image of any element of A.

A function f : A → B is one-to-one if distinct elements of A have distinct images in B. Symbolically, f is one-to-one if a₁, a₂ ∈ A and a₁ ≠ a₂ imply that ƒ(a₁) ≠ ƒ(a₂). It is also logically equivalent to define a function f : A → B to be one-to-one if whenever ƒ (a₁) = ƒ(a₂), then a₁ = a₂ . If A = {a, b, c, d} and B = {1, 2, 3, 4, 5}, then the function f = {(a, 1), (b, 4), (c, 5), (d, 4)} is not one-to-one, since b and d have the same image, i.e., ƒ(b) = ƒ(d).

Let A = {a₁, a₂, a₃, a₄} and B = {b₁, b₂, b₃, b₄}. Then ƒ = {(a₁, b₃), (a₂, b₂), (a₃, b₄), (a₄, b₁)} is a one-to-one function from A onto B. You might already have observed that if ƒ is a one-to-one function from a set A onto a set B, then f describes a pairing of the elements of A with the elements of B. This is always the case. Thus, a one-to-one mapping from a set A onto a set B is possible only when A and B have the same number of elements.

Of the many methods of combining two functions into a single function, the most important method is composition of functions. If ƒ : A → B and g : B → C, then the composition of f and g, denoted g ⃘ f : A → C, is defined by (g ⃘ f) (a) = g(ƒ(a)) for every a ∈ A. As an illustration, we let

A = {a₁, a₂, a₃}, B = {b₁, b₂, b₃, b₄}, C = {c1, c₂, c₃},

ƒ= {(a₁, b₃), (a₂, b₁), (a₃, b₁),

and

g = {(b₁, c₂), (b₂, c₃), (b₃, c₃), (b₄, c₁)}.

Then

g ⃘ ƒ = {(a₁, c₃), (a₂, c₂), (a₃, c₂)}.

The following theorems give two of the most important results dealing with composition.

Theorem A.4

Let f be a function from A onto B and let g be a function from B onto C. Then g ⃘ f is a function from A onto C.

Proof

We must show that every element of C is the image of at least one element of A under the function g ⃘ f. Let c₀ ∈ C. Since g is a function from B onto C, there exists an element b₀ ∈ B such that g(b₀) = c₀. Also, since f is a function from A onto B, there is an element a₀ ∈ A such that f(a₀) = b₀. We now claim that c₀ is the image of a₀ under the composite function g ⃘ f. To see this, we need only observe that

(g ⃘ f) (a₀) = g(f(a₀)) = g(b₀) = c₀ .

Theorem A.5

Let f be a one-to-one function from A into B, and let g be a one-to-one function from B into C. Then g ° f is a one-to-one function from A into C.

Proof

We use the alternate, but equivalent, definition of one-to-one function. Therefore, let a₁, a₂ ∈ A and suppose (g ⃘ f)(a₁) = (g f)(a₂). We must verify that a₁ = a₂ - From the given equation, we have g(ƒ(a₁)) = g(ƒ(a₂)), and since g is a one-to-one function, it follows that ƒ(a₁) = ƒ(a₂). Now we may apply the hypothesis that ƒ is one-to-one and arrive at the desired conclusion that a₁ = a₂. ▋

If A is a nonempty set and ƒ : A → A is a one-to-one function which is also onto, then ƒ is called a permutation of A. For example, if A = {a₁, a₂, a₃, a₄} and ƒ = {(a₁, a₃), (a₂, a₄), (a₃, a₁), (a₄, a₂)}, then ƒ is a permutation of A. Note that a permutation of a set is a rearrangement of the elements of a set. The above function ƒ rearranges (or permutes) the elements of the above set A as follows:

original order: a₁ a₂ a₃ a₄

rearrangement: a₃ a₄ a₁ a₂.

This permutation is one of 24 permutations that exist on the set A = {a₁, a₂, a₃, a₄}.

Problem Set A.4

22. Give an example of two sets A₁ and B₁ and a function ƒ₁ : A₁ → B₁ such that ƒ₁ is onto but not one-to-one.

23. Give an example of two sets A₂ and B₂ and a function ƒ₂ : A₂ → B₂ such that ƒ₂ is one-to-one but not onto.

24. Determine all permutations of the set V = {v₁, v₂, v₃, v₄}.

25. Let f be a one-to-one function from a set A onto a set B. Define the relation ƒ⁻¹ = {(b, a)|(a, b) ∈ ƒ}. Show that ƒ⁻¹ is a one-to-one function from B onto A. (ƒ⁻¹ is called the inverse of ƒ.)

26. Let S be the set of all nonempty finite sets. Let A₁, A₂ ∈ S and define a relation R on S by (A₁, A₂) ∈ R if there exists a one-to-one mapping from A₁ onto A₂. Show that R is an equivalence relation on S. Describe the equivalence classes.

A.5 Theorems and Proofs

We have seen a few examples of theorems and proofs in this Appendix; the text itself contains many more. One of the chief difficulties in learning mathematics is understanding proofs; however, this is ordinarily not nearly as difficult as inventing proofs of your own. Unfortunately, inventing proofs is something which cannot be taught, in general. Constructing proofs is commonly learned through experience, by first trying to understand and then imitating the proofs of others. This, hopefully, leads to the creation of original proofs.

Certainly, you have little hope of proving a theorem if you do not have a sound understanding of the statement of the theorem. All theorems can be stated in the form of an implication “If P, then Q,” where P and Q denote statements which are true or false, but not both. The statement P is the hypothesis of the theorem and Q is the conclusion. Implications are special kinds of statements, and therefore are true or false themselves. Theorems are true implications which are usually of special interest.

We often attempt to prove the implication “If P, then Q” by assuming that P is true and then trying to verify that Q is true. If we accomplish this, we have a direct proof of the implication. It is also logically correct to assume that Q is false and then show that P is false. This is an indirect proof of the implication. As a variation of this method, we may assume that P is true and that Q is false (hoping, of course, that this is impossible) and then attempt to show that P is false. Since P cannot be both true and false, we have proved the implication by contradiction.

Example A.3

We illustrate these various proof techniques with a simple example. We begin by remarking that every integer is even or odd. If x is an even integer, then x = 2n for some integer n. For example, 6 and − 10 are even integers since they can be expressed as twice an integer; in particular, 6 = 2·(3) and −10 = 2 · (− 5). An odd integer y can be expressed as y = 2m + 1, where m is an integer. For odd integers −5 and 17, we have −5 = 2(−3) + 1 and 17 = 2(8) + 1. We can also say that x is even if x = 0 (mod 2) and y is odd if y ≡ 1 (mod 2). With these remarks in mind, we are now prepared to give three proofs of the following elementary result.

Theorem

Let x be an integer. If x is even, then y = x + 5 is odd.

Direct Proof

Assume x is an even integer. Then x = 2n for some integer n. So we have

y = x + 5 = 2n + 5 = (2n + 4) + 1 = 2(n + 2) + 1.

Since m = n + 2 is an integer, it follows that y = 2m + 1, where m is an integer. Therefore, y is an odd integer. ▉

Indirect Proof

Assume y = x + 5 is not an odd integer. Then y must be even. Therefore y = x + 5 = 2n, where n is an integer.

Hence,

x = 2n − 5 = (2n − 6) + 1 = 2 (n − 3) + 1.

Since m = n − 3 is an integer, we have x = 2m + 1 for some integer m. Thus, x is odd; that is, x is not even. ▉

Proof by Contradiction

Assume x is an even integer. Then x = 2n for some integer n. Suppose that y = x + 5 is not odd; thus, y is even so that y = x + 5 = 2m for some integer m. Therefore,

x = 2m − 5 = (2m − 6) + 1 = 2(m − 3) + 1.

Since k = m − 3 is an integer, it follows that x = 2k + 1 for some integer k, so x is odd. This is a contradiction. ▋

We next consider some of the common terminology used in the statements of theorems. The theorem

“If P, then Q”

may also be stated

“P only if Q”

as well as

“P is sufficient for Q”

or

“Q is necessary for P.”

It is often very difficult to see that these four statements all say the same thing. In order to get a little better feeling for this, let us take a statement and rephrase it in three ways. Consider the statement

“If I get all A’s this semester, then I will get an A in this course.”

This statement may be rephrased as follows:

“I will get all A’s this semester only if I get an A in this course.”

“For me to get an A in this course, it is sufficient for me to get all A’s this semester.”

“For me to get all A’s this semester, it is necessary for me to get an A in this course.”

The converse of “If P, then Q” is the implication “If Q, then P.” The truth or falseness of “If P, then Q” does not imply the truth or falseness of its converse. From what we have said, the converse “If Q, then P” may also be stated as “Q only if P”; “Q is sufficient for P”; or “P is necessary for Q.” Hence, if the implication “ If P, then Q” and its converse “If Q, then P” (or equivalently, “P if Q”) are both true, then we may state these two implications as “P if and only if Q” and “P is necessary and sufficient for Q.”

We illustrate some of these terms with an example from geometry.

Example A.4

The implication “If a triangle has three equal sides, then it has two equal sides” is true. (It is highly doubtful that this implication would be classified as a theorem.) We may also state this implication as “A triangle has three equal sides only if it has two equal sides.” Using the words “sufficient” and “necessary,” we may say “A sufficient condition for a triangle to have two equal sides is that it have three equal sides” or “A necessary condition for a triangle to have three equal sides is that it have two equal sides.” The converse of the implication is “If a triangle has two equal sides, then it has three equal sides.” The converse is false.

Problem Set A.5

27. Prove the implication “If x is an odd integer, then y = x − 3 is an even integer” using the three proof techniques: direct proof, indirect proof, proof by contradiction.

28.

Give an indirect proof of the following result: “Let x and y be integers. If x is even, then x + 2y is even.”

Is the converse of the statement in (a) true or false?

29. Give a proof of the following result: “If x = 3, then x² = 9.” What type of proof did you use?

30. State the implication “If x = 3, then x² = 9” using the phrases

only if; (b) sufficient; and (c) necessary.

31. Give an example of a nonmathematical implication of the form “If P, then Q,” where P and Q are statements. Then rewrite the implication using the phrases (a) only if; (b) sufficient; and (c) necessary.

32. The implication “If a triangle has three equal sides, then it has three equal angles” and its converse are both true. State the implication and its converse as a single statement using the phrases (a) “if and only if”; and (b) “necessary and sufficient.”

A.6 Mathematical Induction

One of the most important and most useful proof techniques is referred to as mathematical induction. Before describing this technique, we discuss some properties of integers.

It is a property of the set N of positive integers that they are well-ordered, i.e., every nonempty subset S of N has a smallest (or least) element. For example, the least element of N itself is the integer 1. For the integer m, we introduce the notation

Nm = {x|x ∈ Z, x ≥ m}.

The set Nm is also well-ordered. Using this fact, we establish the following result.

Theorem A.6

Let S be a subset of Nm with the properties:

m ∈ S;

If x ∈ S, then x + 1 ∈ S.

Then S = Nm.

Proof

We prove this result by contradiction. Assume that S ≠ Nm. Then there exists a nonempty subset S‘ of Nm consisting of all the elements of Nm which do not belong to S. Since S′ ⊆ Nm and S’ ≠ ∅, it follows that the set S′ has a least element, say k. By property (1), m ∈ S; therefore, m ∉ S′, implying k ≠ m and k > m. Because k is the least element of S′ and since k − 1 ≥ m, it follows that k − 1 ∈ Nm and k − 1 ∉ S’, so k − 1 ∈ S. Using the fact that k − 1 ∈ S, we conclude, by property (2), that (k − 1) + 1 = k ∈ S. However, then k ∈ S’ and k ∈ S, which is impossible. Thus, we have arrived at a contradiction. This implies that our initial assumption that S ≠ Nm is incorrect, yielding the desired result S = Nm. ▋

With the aid of Theorem A.6, we can now establish the result we are primarily interested in.

Theorem A.7

First Principle of Mathematical Induction

Let m be an integer, and let Sm, Sm+1, Sm+2, ... be statements with the properties:

Sm is a true statement;

If Sk is a true statement, then Sk+1 is a true statement.

Then each of the statements Sm, Sm+1 Sm+2, ... is true.

Proof

We define a set S of integers as follows:

S = {i|i ≥ m, Si is a true statement}.

Since Sm is a true statement, it follows that m ∈ S. If k ∈ S, then, necessarily, Sk is true. However, by property (2), Sk+1 is also true, which implies that k + 1 ∈ S; that is, if k ∈ S, then k + 1 ∈ S. Therefore, because S ⊆ Nm and S satisfies the two properties of Theorem A.6, we conclude, by Theorem A.6, that S = Nm. Hence, for every i ≥ m, Si is a true statement. ▋

The First Principle of Mathematical Induction is often used for the case m = 1. We state this special case:

Corollary

First Principle of Mathematical Induction

Let S₁, S₂, S₃, ... be statements with the properties:

S₁ is a true statement;

If Sk is a true statement, then Sk+1 is a true statement.

Then each of the statements S1, S₂, S₃, ... is true.

As a simple (and common) illustration of the First Principle of Mathematical Induction, we consider the mathematical statement

Sn : 1 + 3 + 5 + · · · + (2n − 1) = n².

We show that Sn is a true statement for every positive integer n. First, since 1 = 1², S₁ is true. Next, suppose that

Sk: 1 + 3 + 5 + ··· + (2k − 1)= k²

is a true statement. We show that

Sk+1 : 1 + 3 + 5 + ··· +(2k −1 ) + (2k + 1) = (k + 1)²

is a true statement. Since 1 + 3 + 5 + ··· + (2k − 1) = k², it follows that

[1 + 3 + 5 + ··· + (2k − 1)] + (2k + 1) = k² + (2k + 1);

however, k² + (2k + 1) = (k + 1)², so Sk+1 is a true statement. Hence Sn is a true statement for every positive integer n.

A variation of the First Principle of Mathematical Induction is also very useful. Since its proof is similar to the proof of Theorem A.7, we state this result without proof.

Theorem A.8

Second Principle of Mathematical Induction

Let m be an integer, and let Sm, Sm+1, Sm+2, ... be statements with the properties:

Sm is a true statement;

If Si is a true statement for each i, m ≤ i ≤ k, then Sk+1 is a true statement.

Then each of the statements Sm, Sm+1, Sm+2, ... is true.

Problem Set A.6

33. Which of the following sets are well-ordered? (Q denotes the set of rational numbers, i.e., fractions.)

N

Z

S = {n | n ∈ Z, n ≥ −10}

S = {n | n ∈ Q, n ≥ −10}

the open interval (−2, 2)

the closed interval [−2, 2]

S = {−2, −1, 0, 1, 2}

S = {p | p is a prime} = {2, 3, 5, 7, 11, 13, 17, ...}

S = {1/2, 1/3, 1/4, 1/5, ...}

S = {1/2, 2/3, 3/4, 4/5, ...}

S={x | x ∈ Q, −1 ≤ x ≤ 1}.

34. Prove that if A is any well-ordered set of numbers and B is a nonempty subset of A, then B is also well-ordered.

35. Prove that the statement

Sn: 1 + 2 + 3 + ··· + n = n(n + 1)/2

is true for every positive integer n.

36. Prove that

Sn: 1² + 2² + 3² + ··· + n² = n(n + 1)(2n + 1)/6

is true for every positive integer n.

37. Prove that

1³ + 2³+ 3³ + ··· + n³ = n²(n + 1)²/4

for every positive integer n.

38. Prove that

1² + 3² + 5² + · · · + (2n − 1)² = (4n³ − n)/3

for every positive integer n.

39. Prove that

for every positive integer n.

40. Prove that

1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) = n(n + 1)(2n + 7)/6

for every positive integer n.

41. Prove using mathematical induction that the total number of distinct subsets of a set with n elements is 2n.

42. State Theorem A.8 for the special case m = 1.

43. Prove Theorem A.8.

44. Define x₁ = 1, x₂ = 2, and xn+2 = xn+1 + xn for n ≥ 1.

Prove that xn is defined for every positive integer n.

Prove that 4nxn < 7” for every positive integer n.

45. Prove that 2n > n for every integer n ≥ 0.

46. Prove the following implication for every positive integer n: If x₁, x₂, · · · , xn are any n numbers such that x₁ · x₂ · · · xn = 0, then at least one of the numbers x₁, x₂, . . . , xn is 0. (Use the result that if the product of two numbers is 0, then at least one of the numbers is 0.)

47. Prove that n! > 2” for every integer n ≥ 4. [Note: n! = n(n − 1)(n − 2) · · · 3 · 2 · 1.]

48. Prove that 2n > n³ for every integer n ≥ 10.

49. It is known that if an integer n ( ≥ 2) is not prime, then there exist integers a and b with 1 < a < n and 1 < b < n such that n = ab. Prove that every integer n ≥ 2 is either prime or a product of primes.

50. If n ≥ 2, prove that the number of prime factors of n is less than 2 In n = 2 loge n.

51. Prove that for n ≥ 2, the maximum number of points of intersection of n distinct lines in the plane is n(n − 1)/2.

52. Let ƒ(x) = In x = loge x. Prove that for every positive integer n, the nth derivative of ƒ(x) is given by

53. Let ƒ(x) = xe−x. Prove that ƒ(n)(x) = (−1)ne−x(x − n) for every positive integer n.

54. Let U be a universal set. Prove that if A₁, A₂, · · · An(n ≥ 2) are any subsets of U, then

55. Let U be a universal set. Prove that if A₁, A₂, . . , An (n ≥ 2) are any subsets of U, then

Answers, Hints, and Solutions to Selected Exercises

Chapter 1

Problem Set 1.2

(page 8)

5. The formula probably does not hold for any other values of n.

7. dT/dt = k(T − 70).

11. What value of x produces the maximum profit?

13. You could list the results of the various tosses by R₁ R₂ R₃ R₄, where Ri (i = I, 2, 3, 4) is the result on toss i. Hence, Ri = H (heads) or T (tails) for i = 1, 2, 3, 4. The total number of possible “combinations” is 16. Of these, 6 give two heads and two tails, and 10 do not. So, on the average, 6/16 of the time you win $11, while 10/16 of the time you pay $10. The main question to ask is whether you are likely to win or lose money.

Problem Set 1.3

(page 12)

15.

R = {(u₁, u₂), (u₂, u₁), (u₁, u₄), (u₄, u₁), (u₁, u₅), (u₅, u₁), (u₂, u₃), (u₃, u₂), (u₃, u₅), (u₅, u₃), (u4, u₅), (u₅, u₄)}.

17. 0,1,2,3.

19. Yes; let V = {u₁, u₂, u₃} and E = {u₁u₂, u₁u₃, u₂u₃}.

No; for if V = {u₁, u₂, u₃, u₄}, then u₁u₂, u₃u₄ ∈ E, but u₁u₂ and u₃u₄ are not adjacent.

21. n − 1.

23. See the example in Exercise 19.

Problem Set 1.4

(page 15)

27. For any two vertices, determine whether it is possible to proceed from one to the other by a sequence of edges.

29. For graph G₁, let V(G₁) represent the Student Council members. Join two vertices of G₁ by an edge if and only if the two individuals belong to the same committee. For graph G₂, let V(G₂) represent the ten committees. Join two vertices of G₂ by an edge if and only if the two committees have some members in common. (There is at least one other natural graph G₃ possible here.)

Problem Set 1.5

(page 18)

33. (i) 6; (ii) 12; (iii) 20; (iv) n(n − 1).

35. You should be able to get from any place to any other place. Yes, this could be determined from the digraph.

Chapter 2

Problem Set 2.1

(page 30)

1. deg v₆ = 1; deg v₁ = deg v₇ = deg v₈ = 2: deg v₂ = deg v₃ = deg v₄ = 3; deg v₅ = 4. p = 8, q = 10.

3. A graph of order 5 cannot have a vertex of degree 5.

5. Yes: the number of degrees listed is the order of G. The sum of the degrees is twice the size of G.

7. (a) K₃ (b) K₂ (c) none (d) K₁ (e) K₂

(f) the graph having order two and size zero.

9. q = pr/2: for Kp, q = p(p − 1)/2.

11. Km+1 or Kn+1. If m and n are both required degrees, let G be the “disjoint” union of Km+1 and Kn+1.

13. Hint: Represent this situation by a graph where the vertices correspond to the people and each edge represents a handshake. Now consider the degrees of this graph.

Problem Set 2.2

(page 38)

15.

φ(u₁) = u₂, φ(v₁) = v₂, etc.

θ(u₂) = u₁, θ(v₂) = v₁, etc.

17. No: otherwise, this would contradict Theorem 2.4.

19. There are several ways of doing this. One possible hint: F₁ contains pairs of nonadjacent vertices (such as u₁ and u₄) which are mutually adjacent to two vertices. F₂ does not have this property.

21. Hint: G₃ is isomorphic to G₁.

23. Additional Hint: Assume that each subset Si of S has less than {n/k} elements. Now show that S has less than n elements.

25. Hint: If a graph has order 4 and size 2, then the two edges may be adjacent or nonadjacent.

Problem Set 2.3

(page 43)

27.

29.

31. No; every component must have at least one vertex.

33. Additional Hint: If Kx, 1 ≤ x ≤ p − 1, is one component, then Kp−x is the other component. The size of G is f(x) = x(x − 1)/2 + (p − x)(p − x − 1)/2. Now, minimize ƒ(x).

35. Hint: If G is connected, then for every two vertices u and v there is a u−v path, and therefore a u−v walk. To prove the converse statement, show that if there exists a u−v walk in G, then G must contain a u−v path.

37. Additional Hint: Let u₁ be a vertex in a component G₁ of G. Since deg u₁ ≥ (p–1)/2, G₁ has order at least 1 + (p − 1)/2 = (p + 1)/2.

39. One possible circuit is C : v₅, v₄, v₂, v₅, v₆, v₃, v₅.

V(H) = {v₂, v₃, v4, v₅, v₆};

E(H) = {v₂v₄, v₂v₅, v₄v₅, v₃v5, v₃v₆, v₅v₆}.

41. Hint: See Exercise 35.

43. Neither; no edge is repeated in a circuit or cycle.

Problem Set 2.4

(page 47)

45. Cut-vertices: v₄, v₅, v₆. Bridges: v₁v₄, v₅v₆.

47.

By the Pigeonhole Principle, there is a component containing {11/2} = 6 vertices.

Let V(G) = {v, v₁, v₂, . . . , v₁₀} and E(G) = {vv₁, vv₂, . . . , vv₁₀}.

49.

51. Yes. (Hint: First show that if e lies on a circuit of G, then e lies on a cycle of G.)

53.

55. See the solution of Exercise 49.

57.

59. Hint: Let e = uv. Since G is not isomorphic to K₂, at least one of u and v has degree at least two. Suppose deg u ≥ 2. The graph G − e has two components, one containing u and the other containing v. Show that G − u is disconnected.

Chapter 3

Problem Set 3.1

(page 61)

1. G₁ traversable; G₂ neither; G₃ traversable; G₄ neither; G₅ eulerian.

3. G is traversable.

5. A connected multigraph G with exactly four odd vertices contains two edge-disjoint trails such that every edge of G belongs to one of these trails. (Hint for proof: Let u and v be two distinct odd vertices of G, and consider G + uv.)

7. Yes. (Hint: Model this situation with a graph.)

9. No. (Hint: Model this situation with a graph.)

11. The murderer is (gasp)—James Bomb! The graph which models this problem is traversable; however, the vertex corresponding to the exterior of the house is even. This implies that it is not possible to enter the house, go through each door exactly once, and then leave the house. Hence, the gardener lied. However, this does not prove that the gardener killed the Count. Indeed, from the information available, the only way James Bomb could possibly know who murdered the Count is if he committed this terrible crime himself.

13. Answer to first question: No.

15. Hint: If G is connected and its edge set can be partitioned into cycles, then each vertex v of G belongs to a certain number of cycles. What can be said about deg v? To show the converse statement, let G be an eulerian graph. Thus, G contains an eulerian circuit. Now use the fact that every circuit contains a cycle.

Problem Set 3.2

(page 73)

17.

19. Hint: Find a hamiltonian cycle in the graph of the cube.

21. Consider the following graph G. Let H = K(p–1)/2. Define G to be two disjoint copies of H together with a new vertex v adjacent to all vertices in both copies of H.

23. False. To verify this, an example must be given.

25. Additional Hint: The hamiltonian cycle of G cannot contain two consecutive vertices labeled M or two consecutive vertices labeled W.

27. The graph of Figure 3.21 is not hamiltonian. (Hint: Assume this graph is hamiltonian, and obtain a contradiction.)

29. Hint: Consider two cases, depending on whether mn is even or odd.

31. Beginning with city A, the hamiltonian cycle obtained by always proceeding to the next city using the least expensive route is A, B, C, D, E, A. The cost of this cycle is $270. Now determine four other cycles, one beginning at each of B, C, D, and E, respectively. Show that there exists a hamiltonian cycle whose cost is less than the cost of each of these five cycles.

Chapter 4

Problem Set 4.1

(page 87)

1. (a) 1 (b) 1 (c) 2 (d) 3 (e) 6.

The six trees of order 6 are

3. Yes. K₁ and K₂ are the only regular trees.

5.

7. Let G₁, G₂, . . . , Gk be the k components of G. Thus, each component is a tree. If Gi has order pi and size qi, for each i = 1, 2, ..., k, then p₁ + p₂ + · · · + pk = p, q₁ + q₂ + · · · + qk = q, and qi=pi–1. Therefore,

9. If G has no cycles, then G is a tree. Next, suppose that G has cycles. We can obtain a tree T by deleting edges from G; namely, delete an edge e₁ on a cycle of G, producing G–e₁. If G − e₁ is not a tree, then we select an edge e₂ on a cycle of G, producing G − e₁ − e₂. We continue this procedure until a tree T is produced. But T has order p and less than p − 1 edges. This is impossible for a tree.

11. Since G is a forest, G has no cycles. Assume that G is not a tree. Then G hascomponents G₁, G₂, . . . ,Gk, where k ≥ 2. By Exercise 7, q = p − k. Since q = p − 1, it follows that k = 1, giving us a contradiction.

13.

The four economy trees are:

One possible decision is not to have track between that pair of cities among {A, B}, {B, C}, {C, D}, and {D, A} which ordinarily has the least railroad traffic.

(i) Construct track between E and any one of A, B, C, and D.

(ii)

Yes.

17. Hint: Represent this situation by a graph whose vertices correspond to the prison cells and the exterior. An edge represents the existence of a gate between the appropriate cells, or a cell and the exterior.

Problem Set 4.2

(page 95)

19. (a) 1/6 (b) 1/6

21. Answer for (b): 6/16.

23.

The probability of A winning the playoff is

Problem Set 4.3

(page 102)

25. The critical path depends on the times assigned.

27. Label the digraph as follows:

If this is an activity digraph, then C may start immediately after A is completed. However, C cannot start until B is completed, and B cannot start until A is completed. Thus, C cannot start after A is completed.

Chapter 5

Problem Set 5.1

(page 113)

3. 9 − d₁, 9–d₂, . . . 9 − d₁₀.

5. A cycle of order 5.

7.

A path of order 4.

K₂ has one edge; K₃ has three edges. Since these complete graphs have odd size, each graph G of order 2 or 3 has size unequal to that of , so G is not isomorphic to .

9. It means that there exists a positive integer p such that for any graph G of order p, either G contains Km or contains Kn.

11. K₆ is a subgraph of K₇. Since r(K₃, K₃) = 6, K₆ contains a red K₃ or a blue K₃. Therefore, K₇ contains a red K₃ or a blue K₃.

13.

r(P₃, P₃) = 3. Proof: r(P₃, P₃) > 2 since no matter how the edge of K₂ is colored, K₂ contains neither a red P₃ nor a blue P₃. If the edges of K₃ are colored red or blue, at least two of the three edges are colored the same. If red, then a red P₃ is produced; otherwise, a blue P₃ is produced.

r(P₃, K₃) = 5.

15. Six people. (Hint: Represent the situation as a graph.)

Problem Set 5.2

(page 120)

17.

19. Hint: If the cardinalities of two vertex subsets are x and p − x, then the maximum size is f (x) = x(p − x). Now maximize f(x) over all permissible values of x.

21. Hint: Assume that G is r-regular; that |V₁| = m; and that |V₂| = n. Now count (i) the number of edges of G incident with vertices in V₁, and (ii) the number of edges of G incident with vertices in V₂.

23. Hint: Consider each vertex of V₁ individually. and investigate the possibility of a function f: V₁ → V₂.

25. Hint: Represent the situation as a graph and apply Theorem 5.4.

27. Five applicants.

Chapter 6

Problem Set 6.1

(page 131)

1. One possible argument: The pseudograph of Figure 6.5 has 12 edges. If this pseudograph contained three edge-disjoint, 2-regular spanning sub-pseudographs, then they would necessarily use all 12 edges. One of these sub-pseudographs contains the loop (labeled 1) at W and another contains the loop (labeled 2) at G. There do not exist two edges joining R and B, one labeled 3 and one labeled 4, so that these two loops belong to distinct sub-pseudographs. Hence, the sub-pseudograph containing the loop at W must contain a triangle on R, B, and G whose three edges are labeled 2, 3, and 4. However, there is no edge joining R and G. Contradiction!

3. No solution. (Hint: Show that there is no 2-regular spanning sub-pseudograph of the pseudograph which contains the edge labeled 3 joining W and B. Then show that there is none containing the edge labeled 3 joining R and G.)

5. See Exercise 3.

7. No.

9. No.

11. 41,472.

Problem Set 6.2

(page 135)

13. Six moves.

15. There is no knight’s tour of the 4-by-5 chessboard. To see this, begin with the four corner squares.

Problem Set 6.3

(page 139)

19. The hamiltonian cycle is (0, 0, 0), (1, 0, 0), (1, 0), (0, 1, 0), (0, 1, 1), (1, 1, 1), (1,0, 1), (0, 0, 1), (0,0,0).

Problem Set 6.4

(page 144)

21. Hint: We can show this by considering cases. Necessarily, any trail from (3, 3) to (0, 0) which alternates positive and negative edges must first enter (1, 0) or (2, 0) by means of a positive edge. Determine the shortest such trail from (3, 3) to (2, 0) and from (2, 0) to (0, 0).

23. Hint: One possibility is to get all the women into town first.

Chapter 7

Problem Set 7.1

(page 152)

1. If G is hamiltonian, we may select the cycle C in the proof as a hamiltonian cycle. In this case, every vertex of G lies on C, and it is not necessary to consider the situation where there are vertices not belonging to C.

3. Since the graph G of Figure 7.3 contains no bridges, it follows, by Theorem 7.1, that G is orientable.

5. Yes. A graph with cut-vertices need not contain bridges.

7. The street system can be modeled by the following graph G. Since G contains no bridges, G is orientable. The strongly connected digraph D is obtained by assigning directions to the edges of G.

9. Let u be a vertex of G. Direct the edges of G incident with u toward u, and direct any other edges of G in any manner. The resulting digraph D is not strongly connected, since there is no path from u to any other vertex of D.

Problem Set 7.2

(page 159)

11. A tournament T, is isomorphic to a tournament T₂ if there exists a one-to-one mapping φ from the vertex set of T₁ onto the vertex set of T₂ such that for every two distinct vertices u and u of T₁, (u, v) is an arc of T₁ if and only if (φ(u), φ(v)) is an arc of T₂.

13. (a), (b) . (c) p(p − 1)/2.

15. Exactly one of the arcs (u, v) and (v, u) belongs to T. If (u, v), for example, is an arc of T, then d(u, v) = 1 and d(v, u) ≥ 2.

17.

It is possible for each team to win twice and lose twice, as shown in the following tournament:

Suppose it is possible for all six teams to tie for first place. Then each team has the same number n of victories. In the entire tournament, the total number of victories is 6n = 15, implying that n = , which is impossible.

19. Examples with a five-team tournament are given below.

T₂

Problem Set 7.3

(page 167)

25. Councilman Adams would have been elected mayor, since he would have received more votes than the other two candidates. We could describe this by a tournament where (u, v) is an arc if candidate u receives more votes than candidate v.

27. Councilman Carter would have been elected mayor. Since Adams was least preferred by the voters, he would have been eliminated. Between Beane and Carter, Councilman Carter would receive more votes. This could be described by means of the two tournaments:

29. Councilman Carter would have been elected mayor.

31. If nine broadcasters rate State the best team, then their votes would give 90 points to State. Similarly, they would give 81 points to Central. If the tenth broadcaster ranks Central first and does not rank State among the top ten teams, then Central would receive 91 points and State 90 points, giving Central first place in the final rankings.

Chapter 8

Problem Set 8.1

(page 177)

1. If the social system contains only one or two people, then the system is balanced. If the system contains more than two people, it is unbalanced.

3. S is balanced. If S contains no cycles, then S satisfies the condition (trivially) that each of its cycles is positive. Therefore, by Theorem 8.2, S is balanced.

5. Since each of the signed graphs S₁, S₂ . . . ,Sn is balanced for each i (1 ≤ i ≤ n), the vertex set V(S;) can be partitioned as V₁₁ ∪ V₁₂, say, where each edge joining two vertices of V₁₁ or two vertices of V₁₂ is positive and each edge joining a vertex of V₁₁ and a vertex of V₁₂ is negative. Then, it is possible to partition V(S) as V₁ ∪ V₂, where

V₁ = V₁₁ ∪ V₂₁ ∪ · · · ∪ Vn1

and

V₂ = V₁₂ ∪ V₂₂ ∪ · · · ∪ Vn2.

Further, every edge joining two vertices of V₁ or two vertices of V₂ is positive, while each edge joining a vertex of V₁ and a vertex of V₂ is negative. Therefore, S is balanced.

7. Let P‘ be a positive u−v path and let P“ be a negative u−v path. Suppose P’ is the path w₀, w₁, . . . , wn, where w₀ = u and wn = v. The path P″ also begins with vertex w₀ and terminates at wn. Since P′ and P″ are different paths, there must be a vertex wi such that P′ and P″ both begin with w₀, w₁, . . . , wi but the vertex of P″ following wi is not wi+1. Clearly, the w₀−wi subpaths of P’ and P″ contain the same number of negative edges. Let the next vertex of P′ which also belongs to P″ be wj, where j > i. The wi−wj subpath of P′ and the wi−wj subpath of P produce a cycle C₁ in S. If C₁ contains an odd number of negative edges, then C₁ is a negative cycle. Otherwise, the wi−wj subpath of P′ and the wi−wj subpath of P″ both contain an odd number or both contain an even number of negative edges. Therefore, the w₀−wj subpath of P′ and the w₀−wj subpath of P” both contain an odd number or both contain an even number of negative edges. So, exactly one of the wj−wn subpath of P’ and the wj−wn subpath of P′ is even and the other is odd. We may proceed as before to produce a cycle C₂ in S. If C₂ is not negative, there exists a vertex wk(k > j) on both P’ and P″ so that exactly one of the wk−wm subpath of P’ and the wk−wn subpath of P’’ is even and the other is odd. Since paths have a finite number of vertices, eventually we must arrive at a cycle Cm which is negative.

Problem Set 8.2

(page 181)

11. Let S₁, S₂, . . . , Sn be the components of S, where each of the components is clusterable. For i = 1, 2, . . . , n, denote the clusters of Si by Vi1 Vi2 . . . , . Then

V₁ = V₁₁ ∪ V₂₁ ∪ · · · ∪ Vn1,

V₂ = V₁₂ ∪ V₂₂ ∪ · · · ∪ Vn2,

etc. are clusters of S. The minimum number of clusters possible for S is the maximum of the minimum number of clusters of its components.

Chapter 9

Problem Set 9.1

(page 200)

1.

3. For the region R, the vertices of the boundary are v₁, v₂, v₄, v₅, v₆, and the edges of the boundary are v₁v₂, v₂v₆, v₅v₆, v₁v₅, and v₄v₅. For the exterior region, the vertices of the boundary are all of V(G) except v₄ and the edges of the boundary are all of E(G) except v₄ v₅.

5. Suppose G has order p and size q. If G is drawn as a plane graph in any manner whatsoever, then by Theorem 9.1, p − q + r = 2, or r = 2 − p + q; that is, G has 2 − p + q regions.

7. (a) K₃ (b) K(1, 2)

9. False. The following graph G has q = 3p − 6, but G is nonplanar (since K₅ is a subgraph of G).

11. K₁, K₂, K₃, and K₄.

13. The Petersen graph is not planar. It contains a subgraph which is a subdivision of K(3, 3).

Problem Set 9,2

(page 208)

15. The chromatic number of a cycle is 2 or 3, depending on whether its order is even or odd.

17. 4, 5, n + 1; 2, 2, 2,

19. Label G₁ as indicated. Since v₁, v₂, and v₄ produce a triangle, three colors are required to color these vertices. Color v₁ with color 1, v₂ with color 2, and v₄ with color 3. If we color v₃ with 2, v₅ with 1, and v₆ with 3, we will have colored G₁ with three colors. Therefore, χ(G₁) = 3.

21. Four time periods.

Problem Set 9.3

(page 215)

23. 4

25.

27. No; yes, K(3, 3); yes

Chapter 10

Problem Set 10.1

(page 221)

1. The (i, i) entry of A² gives the degree of vi. The (i, j) entry, i ≠ j, of A² gives the number of different vi−vj walks of length two.

3. Define a graph G by letting V(G) = {v₁,v₂, · · · ,vp}. Then vivj is an edge of G if and only if the (i, j) entry of A is 1.

5. aij⁽²⁾, i ≠ j, is the number of vi−vj paths of length two in G, while aij⁽²⁾ = deg vi.

7. If G has order p and size q, then since the incidence matrix is square, p = q. By Exercise 4.10, G contains a cycle.

9. For the graph G of Figure 10.4,

Hint to second question: Consider A(G) and the degrees of G.

Problem Set 10.2

(page 226)

11. 5

13. There are several types of diagrams possible for such an embedding. One such diagram is:

15. Hint: See Exercise 11.

17. Hint: If G is planar, no handles are necessary. Otherwise, draw G on the sphere, where, then, certain pairs of edges cross at points, say P₁, P₂, . . . , Pn. Consider these n points.

Problem Set 10.3

(page 235)

19. Label the vertices of K₂ by 1, 2. Then , where

21. Label the vertex of degree 3 in K(1, 3) by 1, and label the other three vertices by 2, 3, and 4. Then

= {α₀, α₁, α₂, α₃, α₄, α₅},

where

23. Let Pn: 1, 2, . . . , n. Then {α₀, α₁}, where

25. Hint: First show that every automorphism of G is an automorphism of , and conversely.

27. One possibility is Δ = {a}.

29. Using the notation of Exercise 19, we let Δ = {α₁}.

Appendix

Problem Set A.l

(page 242)

1. 8.

3. Additional Hint: If x ∈ V₁ n W₁, then x ∈ V₁ and x ∈ W₁. However, V₁ ⊆ V and W₁ ⊆ W.

5. Hint: First show that U ⊆ W. Then show there exists w ∈ W such that w ∉ U.

Problem Set A.2

(page 245)

7.

All three properties (assuming that two coincident lines are parallel).

Reflexive and symmetric.

Transitive.

9. R = {(a, a), (a, b), (b, c)} is one such example.

11. Symmetric and transitive.

Problem Set A.3

(page 251)

13. A person is born in the same year as himself (or herself). If person A is born in the same year as person B, then B is born in the same year as A. If A is born in the same year as B and B is born in the same year as C, then A is born in the same year as C. Each equivalence class consists of all people born in a particular year.

15. For each a ∈ A, a R a. (It was given that a and b need not be distinct.) Since every two elements are related, a R b implies b R a, and a R b and b R c imply a R c. There is only one equivalence class, containing all elements of A.

17. The distinct elements of Z₂ are

[0] = {0, ± 2, ± 4,. . .} and [1] = {± 1, ± 3, ± 5, . . .}.

The distinct elements of Z₃ are

[0] = {0. ± 3, ± 6, . . . }, [1] = {1,–2, 4,–5, . . . },

and

[2] = {2,–1, 5,–4, . . . }.

19. For each a ∊Z, a + a = 2a ≡ 0 (mod 2), since 2∣2a. Therefore, R is reflexive. If a R b, then a + b ≡ 0 (mod 2); however, a + b = b + a, so b + a ≡ 0 (mod 2), implying that R is symmetric. Assume a R b and b R c. Then a + b ≡ 0 (mod 2) and b + c ≡ 0 (mod 2). Thus 2∣(a + b) and 2∣(b + c), so a + b = 2m and b + c = 2n for some integers m and n. Adding, we obtain a + 2b + c = 2m + 2n, or a + c = 2(m + n − b). Hence 2∣(a + c), so a + c ≡ 0 (mod 2), implying that R is transitive. The distinct equivalence classes are [0] = {0, ±2, ±4, . . .} and [1] = (± 1, ±3, ±5, . . . }.

21. Hint: For transitivity, assume a² ≡ b² (mod 5) and b² = c² (mod 5), implying a² − b² = 5m and b² − c² = 5n. Now add these two expressions. There are three distinct equivalence classes.

Problem Set A. 4

(page 255)

23. Hint: Let A₂ = B₂ = Z. Define ƒ₂(n) = 2n.

25. First we show that ƒ⁻¹ is a function. Let y ∊ B. We need to show that there is a unique x ∊ A such that (y, x) ∊ ƒ⁻¹. Since ƒ is onto, there exists x ∊ A such that ƒ(x) = y. Since ƒ is one-to-one, x is the only element of A whose image is y. Hence x is the only element of A such that (y, x) ∊ ƒ⁻¹. To show ƒ⁻¹ is onto, let a ∊ A. Suppose ƒ(a) = b. Then ƒ⁻¹(b) = a, and ƒ⁻¹ is onto. To show ƒ⁻¹ is one-to-one, assume ƒ⁻¹(b₁) = ƒ⁻¹(b₂). Suppose ƒ⁻¹(b₁) = a₁ and ƒ⁻¹(a₂) = a₂; thus, a₁ = a₂. So ƒ(a₁) = ƒ(a₂), but since ƒ(a₁) = b₁ and ƒ(a₂) = b₂, we get b₁ = b₂.

Problem Set A.5

(page 260)

27. Hint: See Example A.1.

29. If x = 3, then x² = (3)² = 9. Direct proof.

31.

If we win the game, then we are champions. We win the game only if we are champions.
To be champions, it is sufficient to win the game.
To win the game, it is necessary to be champions.

Problem Set A.6

(page 264)

33. (a), (c), (g), (h), (j).

35. S₁ is true since 1 = 1(1 + 1)/2. Assume Sk is true, i.e., assume 1 + 2 + · · · + k = k(k + 1)/2. Consider

implying that Sk+1 is true. By the First Principle of Mathematical Induction, Sn is true for every positive integer n.

37. Hint:

(1³ + 2³ + · · · + k³) +(k + 1)³ = [k²(k + 1)²/4] + (k + 1)³.

39. Hint:

k/(k + 1) + 1/(k + 1)(k + 2) = (k + 1)/(k + 2).

41. We can begin with n = 0. There is one subset of a set with no elements, namely ∅: that is, the number of subsets of a set with 0 elements is 2⁰ = 1. Assume the result is true for any set with k elements, where k ≥ 0. Let A = {a₁, a₂, . . . , ak, ak+1} be an arbitrary set with k + 1 elements. We show that the number of subsets of A is 2k+1. Let B = {a₁ a₂, . . . , ak}. Since B has k elements, there are 2k subsets of B. Since B ⊆ A, each subset of B is a subset of A; in fact, every subset of A not containing ak+1 is a subset of B. Thus there are 2k subsets of A not containing ak+1. The subsets of A containing ak+1 are obtained by taking the union of the subsets of B with {ak+1}; hence there are 2k subsets of A containing ak+1. Therefore, the total number of subsets of A equals 2k+ 2k= 2k+1.

43. Hint: First prove the following result. Let S be a subset of Nm with the properties:

m ∊ S;

If m, m + 1, . . . , k are in S (where k ≥ m), then k + 1 ∊ S.

Then S = Nm.

45. The result is true for n = 0 since 2° = 1 > 0. Assume 2k > k, where k ≥ 0. We show that 2k+1 > k + 1. Observe that 2k+1 = 2.2k = 2k + 2k > k + 1, since 2k > k and 2k ≥ 1 for k ≥ 0.

47. The result is true for n = 4 since 4! = 24 > 2⁴ = 16. Assume that k! > 2k, where k ≥ 4. Then (k + 1)! = (k + 1)k! > 2 · k! (since k ≥ 4). Since k! > 2k it follows that 2 · k! > 2 · 2k = 2k+1.

49. The result is true for n = 2, since 2 is prime. Let k(≥2) be an integer, and assume that all integers 2, 3, . . . , k are either prime or can be written as a product of primes. Consider k + 1. If k + 1 is prime, the desired result follows. If k + 1 is not prime, then there exist integers a and b with 1 < a < k + 1 and 1 < b < k + 1 such that k + 1 = ab. By the induction hypothesis, each of a and b is prime or a product of primes. Hence k + 1 = ab is a product of primes.

51. If two distinct lines intersect, then there is exactly one point of intersection, and 1 = 2(2 − 1)/2. Assume that the maximum number of points of intersection of k(≥2) distinct lines in the plane is k(k − 1)/2. Consider a collection of k + 1 distinct lines in the plane. Let l be one of them, and consider the remaining k lines. These k lines intersect in at most k(k − 1)/2 points of intersection. The line l can introduce at most k additional points of intersection. Therefore, all k + 1 lines produce at most k(k − 1)/2 + k = k(k + 1)/2 points of intersection.

53. By the product rule of differentiation from calculus,

ƒ’(x) = xe−x(−1) + e−x = (−1)e−x(x − 1),

and the result is true for n = 1. Assume for k ≥ 1 that

ƒ(k)(x) (−1)ke−x(x − k).

By the product rule, we have

55. For n = 2, the result is Theorem A.1(b). Assume the result for n = k(≥2). Consider

Index

Activity

Activity digraph

Adjacency matrix

Adjacent edges

Adjacent vertices

Adult

Arc

“Around the World” game

Asymmetric relation

Automorphism of a graph

Automorphism group

Balanced signed graph

Balanced social system

Bipartite graph

Boundary of a region,

on a plane

on a torus

Bridge

Cannibals and Missionaries Problem

Cardinality of a set

Cartesian product of sets

Cayley color graph

Child

Chromatic number

Circuit

Clique

Cluster

Clusterable signed graph

Clusterable social system

Coloring

n-coloring

Complement of a graph

Complement of a set

Complementary graph

self-complementary graph

Complementary transaction

Complete graph

Component

Composition of functions

Conclusion of an implication

Congruence modulo n

Connected graph

Connected vertices

Contradiction, proof by

Converse

Critical path

Critical path method

n-Cube

Cut-vertex

Cycle

Cyclic group

Dancing Problem

Deficiency

Degree

DeMorgan’s Laws

Digraph

activity

symmetric

Dihedral group

Direct proof

Directed edge

Directed graph. See Digraph

Directed network

Disconnected graph

Disjoint sets

Distance in a digraph

Divides (integers)

Eccentric Hosts Problem

Economy tree

Edge

directed

Edge set

of a digraph

of a graph

Element of a set

Embedding,

on a plane

on a torus

Empty set

Equal sets

Equal walks

Equivalence class

Equivalence relation

Equivalence set

Euler, Leonhard

Eulerian circuit

Eulerian graph

Eulerian multigraph

Eulerian trail

Even vertex

Exterior region

Five Color Theorem

Forest

Four Color Problem

Four Color Theorem

Function

Generator of a group

Graph

Group

of a graph

Group dynamics

Hamilton, Sir William Rowan

Hamiltonian cycle

Hamiltonian graph

Hamiltonian path,

in a digraph

in a graph

Hanoi, Tower of

Houses and Utilities Problem

Hypothesis

Identity

Image

Implication

Incidence matrix

Incident (vertex and edge)

Incident from

Incident to

Indegree

Indirect proof

Induction, mathematical,

First Principle of

Second Principle of

“Instant Insanity”

Integers modulo n

Intersection of sets

Inverse of a function

Irreflexive relation

Isomorphic graphs

Isomorphism

Jealous Husbands Problem

Joins (two vertices)

Knight’s Tour Puzzle

Konigsberg Bridge Problem

Length of path in a digraph

Length of walk

Loop

Loop-digraph

Loop-graph

Map

Mapping

Marriage Problem

Matched

Matching

Mathematical induction,

First Principle of

Second Principle of

Mathematical model

Minimal Connector Problem

Model

mathematical

Multigraph

Multiple edges

n-cube

Necessary condition

Negative cycle

Negative edge

Negative path

Network

directed.

undirected

Nonadjacent edges

Nonadjacent vertices

Noncomplementary transaction

Nondeficient

Null set

Odd vertex

One-to-one function

Onto function

Order of a graph

Ordered pair

Orientable graph

Outdegree

(p, q) graph

Parent

Partition

Path,

in a digraph

in a graph

Perfect graph

Permutation

PERT

Petersen graph

Pigeonhole Principle

Planar graph

Plane graph

Positive cycle

Positive edge

Positive path

Proof,

by contradiction

direct

indirect

by mathematical induction

Probability

Proper subset

Pseudograph

Ramsey number

Receiver

Reflexive relation

Region of a graph,

in a plane

simply connected

in a torus

Regular graph

Relation

equivalence

reflexive

symmetric

transitive

Salesman’s Problem (See also Traveling Salesman’s Problem.)

Self-complementary graph

Set

Signed graph

Simply connected region

Size of a graph

Social system

Spanning tree

Strongly connected digraph

Subdivision

Subgraph

Subset

Sufficient condition

Symmetric digraph

Symmetric relation

Time-length

Toroidal graph

Tournament

Tower of Hanoi

Trail

Transaction

Transactional analysis

Transactional response

Transactional stimulus

Transitive relation

Transmitter

Traveling Salesman’s Problem

Traversable graph

Tree

Undirected network

Union of sets

Universal set

Value of an edge

Value of a tree

Vertex of a digraph

Vertex of a graph

Vertex set,

of a digraph

of a graph

Vertex triple

Walk

Well-ordered set

Wine Bottle Problem