Discrete Mathematics with Graph Theory (3rd Edition) [Hardcover]

To the Student from the Authors

Few people ever read a preface, and those who do often just glance at the first few lines. So we begin by answering the question most frequently asked by the readers of our manuscript: "What does BB mean?" Like most undergraduate texts in mathematics these days, answers to some of our exercises appear at the back of the book. Those which do are marked BB for "Back of Book." In this book, complete solutions, not simply answers, are given to almost all the exercises marked BB. So, in a sense, there is a free Student Solutions Manual at the end of this text.

We are active mathematicians who have always enjoyed solving problems. It is our hope that our enthusiasm for mathematics and, in particular, for discrete mathematics is transmitted to our readers through our writing.

The word "discrete" means separate or distinct. Mathematicians view it as the opposite of "continuous." Whereas, in calculus, it is continuous functions of a real variable that are important, such functions are of relatively little interest in discrete mathematics. Instead of the real numbers, it is the natural numbers 1, 2, 3, . . . that play a fundamental role, and it is functions with domain the natural numbers that are often studied. Perhaps the best way to summarize the subject matter of this book is to say that discrete mathematics is the study of problems associated with the natural numbers.

You should never read a mathematics book or notes taken in a mathematics course the way you read a novel, in an easy chair by the fire. You should read at a desk, with paper and pencil at hand, verifying statements which are less than clear and inserting question marks in margins so that you are ready to ask questions at the next available opportunity.

Definitions and terminology are terribly important in mathematics, much more so than many students think. In our experience, the number one reason why students have difficulty with "proofs" in mathematics is their failure to understand what the question is asking. This book contains a glossary of definitions (often including examples) at the end as well as a summary of notation inside the front and back covers. We urge you to consult these areas of the book regularly.

As an aid to interaction between author and student, we occasionally ask you to "pause a moment" and think about a specific point we have just raised. Our Pauses are little questions intended to be solved on the spot, right where they occur, like this.

Pause 1: Where will you find BB in this book and what does it mean?

The answers to Pauses are given at the end of every section just before the exercises. So when a Pause appears, it is easy to cheat by turning over the page and looking at the answer, but that, of course, is not the way to learn mathematics!

We believe that writing skills are terribly important, so, in this edition, we have highlighted some exercises where we expect answers to be written in complete sentences and good English.

Discrete mathematics is quite different from other areas in mathematics which you may have already studied, such as algebra, geometry, or calculus. It is much less structured; there are far fewer standard techniques to learn. It is, however, a rich subject full of ideas at least some of which we hope will intrigue you to the extent that you will want to learn more about them. Related sources of material for further reading are given in numerous footnotes throughout the text.

To the Student from a Student

I am a student at Memorial University of Newfoundland and have taken a course based on a preliminary version of this book. I spent one summer working for the authors, helping them to try to improve the book. As part of my work, they asked me to write an introduction for the student. They felt a fellow student would be the ideal person to prepare (warn?) other students before they got too deeply engrossed in the book.

There are many things which can be said about this textbook. The authors have a unique sense of humor, which often, subtly or overtly, plays a part in their presentation of material. It is an effective tool in keeping the information interesting and, in the more subtle cases, in keeping you alert. They try to make discrete mathematics as much fun as possible, at the same time maximizing the information presented.

While the authors do push a lot of new ideas at you, they also try hard to minimize potential difficulties. This is not an easy task considering that there are many levels of students who will use this book, so the material and exercises must be challenging enough to engage all of them. To balance this, numerous examples in each section are given as a guide to the exercises. Also, the exercises at the end of every section are laid out with easier ones at the beginning and the harder ones near the end.

Concerning the exercises, the authors' primary objective is not to stump you or to test more than you should know. The purpose of the exercises is to help clarify the material and to make sure you understand what has been covered. The authors intend that you stop and think before you start writing.

Inevitably, not everything in this book is exciting. Some material may not even seem particularly useful. As a textbook used for discrete mathematics and graph theory, there are many topics which must be covered. Generally, less exciting material is in the first few chapters and more interesting topics are introduced later. For example, the chapter on sets and relations may not captivate your attention, but it is essential for the understanding of almost all later topics. The chapter on principles of counting is both interesting and useful, and it is fundamental to a subsequent chapter on permutations and combinations.

This textbook is written to engage your mind and to offer a fun way to learn some mathematics. The authors do hope that you will not view this as a painful experience, but as an opportunity to begin to think seriously about various areas of modern mathematics. The best way to approach this book is with pencil, paper, and an open mind.

To the Instructor

Since the first printing of this book, we have received a number of queries about the existence of a solutions manual. Let us begin then with the assurance that a complete solutions manual does exist and is available from the publisher, for the benefit of instructors.

The material in this text has been taught and tested for many years in two one-semester courses, one in discrete mathematics at the sophomore level (with no graph theory) and the other in applied graph theory (at the junior level). We believe this book is more elementary and written with a far more leisurely style than comparable books on the market. For example, since students can enter our courses without calculus or without linear algebra, this book does not presume that students have backgrounds in either subject. The few places where some knowledge of a first calculus or linear algebra course would be useful are clearly marked. With one exception, this book requires virtually no background. The exception is Section 10.3, on the adjacency matrix of a graph, where we assume a little linear algebra. If desired, this section can easily be omitted without consequences.

The material for our first course can be found in Chapters 1 through 7, although we find it impossible to cover all the topics presented here in the thirty-three 50-minute lectures available to us. There are various ways to shorten the course. One possibility is to omit Chapter 4 (The Integers), although it is one of our favorites, especially if students will subsequently take a number theory course. Another solution is to omit all but the material on mathematical induction in Chapter 5, as well as certain other individual topics, such as partial orders (Section 2.5) and derangements (Section 7.4).

Graph theory is the subject of Chapters 9 through 15, and again we find that there is more material here than can be successfully treated in thirty-three lectures. Usually, we include only a selection of the various applications and algorithms presented in this part of the text. We do not always discuss the puzzles in Section 9.1, scheduling problems (Section 11.5), applications of the Max Flow-Min Cut Theorem, or matchings (Sections 15.3 and 15.4). Chapter 13 (Depth-First Search and Applications) can also be omitted without difficulty. In fact, most of the last half of this book is self-contained and can be treated to whatever extent the instructor may desire.

Chapter 8, which introduces the concepts of algorithm and complexity, seems to work best as the introduction to the graph theory course.

Wherever possible, we have tried to keep the material in various chapters independent of material in earlier chapters. There are, of course, obvious situations where this is simply not possible. It is necessary to understand equivalence relations (Section 2.4), for example, before reading about congruence in Section 4.4, and one must study Hamiltonian graphs (Section 10.2) before learning about facilities design in Section 14.3. For the most part, however, the graph theory material can be read independently of earlier chapters. Some knowledge of such basic notions as function (Chapter 3) and equivalence relation is needed in several places and, of course, many proofs in graph theory require- mathematical induction (Section 5.1).

On the other hand, we have deliberately included in most exercise sets some problems which relate to material in earlier sections, as well as some which are based solely on the material in the given section. This opens a wide variety of possibilities to instructors as to the kind of syllabus they wish to follow and to the level of exercise that is most appropriate to their students. We hope students of our book will appreciate the complete solutions, not simply answers, provided for many of the exercises at the back. By popular demand, we have increased the number of BBs in this second edition by over 60%.

One of the main goals of this book is to introduce students in a rigorous, yet friendly, way to the "mysteries" of theorem proving. Sections 1.1 and 1.2 are intended as background preparation for this often difficult journey. Because many instructors wish to include more formal topics in logic, this edition includes sections on truth tables, the algebra of propositions, and logical arguments (Sections 1.3, 1.4, 1.5, respectively).

Supplements

There is a full Instructor's Solutions Manual (0130920126) free to faculty, available only through Prentice Hall's sales reps and home offices. In addition, there is a student website of activities available by November 1, 2001 at the following address: www.prenhall.com/goodaire. This site is free to all users/purchasers of this text.

New in the Second Edition

The most common (negative) criticism of our first edition was the short treatment of logic and the absence of truth tables. This problem has been remedied with Chapter 1 (previously Chapter 0) completely rewritten and expanded significantly to include new sections on truth tables, the algebra of propositions, and logical arguments. The text now includes more than enough material for instructors who wish to include a substantial unit on formal logic, while continuing to permit a shorter treatment dealing exclusively with the major points and jargon of proofs in mathematics.

The second most common complaint—and every student's favorite—was the shortage of answers in the back of the book. In fact, the first edition contained over 500 solved problem. For the second edition, however, this number has been increased to over 800.

Other features of the second edition include the following:

• A new section (12.5) on acyclic graphs and an algorithm of Bellman
• A shortest path algorithm due to Bellman and Ford which permits negative weight arcs, in the section (11.2) on digraphs
• Algorithms rewritten in a less casual way so as to more closely resemble computer code
• Review exercises at the end of every chapter
• Nonmathematical exercises, often requiring some research on behalf of the reader, asking that answers be written in good clear English, in order to encourage the development of sound writing and expository skills
• A new numbering scheme which will make searching much easier for our readers

Acknowledgments

This book represents the culmination of many years of work and reflects the comments and suggestions of numerous individuals. We acknowledge with gratitude the assistance and patience of our acquisitions editor, George Lobell, and his assistant, Melanie Van Benthuysen; our production editor, Bayani Mendoza de Leon; and all the staff at Prentice Hall who have helped with this project.

We thank sincerely the literally hundreds of students at Memorial University of Newfoundland and elsewhere who have used and helped us to improve this text. Matthew Case spent an entire summer carefully scrutinizing our work. Professors from far and wide have made helpful suggestions. For the current edition, we are especially indebted to Peter Booth, Clayton Halfyard, David Pike, and Nabil Shalaby at Memorial University of Newfoundland. David, in particular, gave us a lot of help for which we are most grateful.

Without exception, each of the reviewers Prentice Hall employed on this project gave us helpful and extensive criticism with just enough praise to keep us working. We thank, in particular, the reviewers of our first edition:

– Amitabha Ghosh (Rochester Institute of Technology)
– Akihiro Kanamori (Boston University)
– Nicholas Krier (Colorado State University)
– Suraj C. Kothari (Iowa State University)
– Joseph Kung (University of North Texas)
– Nachimuthu Manickam (Depauw University)

those of the second edition:

– David M. Arnold (Baylor University)
– Kiran R. Bhutani (The Catholic University of America)
– Krzysztof Galicki (University of New Mexico)
– Heather Gavias (Grand Valley State University)
– Gabor J. Szekely (Bowling Green State University)

and those who prefer to remain anonymous.

Wile this book was eventually typeset by Prentice Hall, it was prepared on the first author's computer using the MathTime and MathTime Plus fonts of Y&Y, Inc. We wish to thank Mr. Louis Vosloo of Y&Y Support for his unusual patience and help.

Most users of this book have had, and will continue to have, queries, concerns, and comments to express. We are always delighted to engage in correspondence with our readers and encourage students and course instructors alike to send us e-mail anytime. Our addresses are edgar@math.mun.ca and michaell@math.mun.ca.

Answers to Pauses

1. BB is found throughout the exercises in this book. It means that the answer to the exercise which it labels can be found in the Back of the Book.

EXERCISES

There are no exercises in this Preface, but there are over two thousand exercises in the rest of the book!

E.G. Goodaire
M.M. Parmenter
edgar@math.mun.ca
michaell@math.mun.ca