** ** Far more "user friendly" than the vast majority of similar books, this volume is truly written with the unsophisticated reader in mind. The pace is leisurely, but the authors are rigorous and maintain a serious attitude towards theorem proving throughout. ** ** Emphasizes "Active Reading" throughout, a skill vital to success in learning how to write proofs. Offers two sections on probability (2.4 and 2.5). Moves material on depth-first search, which previously comprised an entire (very short) chapter, to an earlier chapter where it fits more naturally. Rewrites section on RNA chains to include a new (and easier) algorithm for the recovery of an RNA chain from its complete enzyme digest. Provides true/false questions (with all answers in the back of the book) in every section. Features an appendix on matrices. ** ** A useful reference for mathematics enthusiasts who want to learn how to write proofs.

*"synopsis" may belong to another edition of this title.*

Adopting a user-friendly, conversational—and at times humorous—style, these authors make the principles and practices of discrete mathematics as stimulating as possible while presenting comprehensive, rigorous coverage. Examples and exercises integrated throughout each chapter serve to pique reader interest and bring clarity to even the most complex concepts. Above all, the book is designed to engage today's readers in the interesting, applicable facets of modern mathematics. More than 200 worked examples and problems, as well as over 2500 exercises are included. Full solutions are provided in the back of the book. More than 150 Pauses—short questions inserted at strategic points—are included. Full solutions to Pauses are included at the end of each section. For educators in area of discrete mathematics.

**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 "**B**ack of **B**ook." 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

*"About this title" may belong to another edition of this title.*

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Quantity Available: 13

Seller:

Rating

**Book Description **Condition: New. Brand new book. This is an international edition textbook with identical content as the US version. We ship all our orders from CA/IL, USA (depending on your address) and NOT from Asia! Choose expedited shipping for superfast delivery with tracking. Seller Inventory # 9780131679955

Published by
Prentice Hall

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Hardcover
Quantity Available: > 20

Seller:

Rating

**Book Description **Prentice Hall. Hardcover. Condition: New. 0131679953 Paperback. Book Condition: New. This is an International Edition. Brand new. Seller Inventory # INDMKT-9789332549777

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Paperback
Quantity Available: 15

Seller:

Rating

**Book Description **Paperback. Condition: NEW. This is an International Edition. Brand New, Paperback, Delivery within 6-14 business days, Similar Contents as U.S Edition, ISBN and Cover design may differ, printed in Black & White. Choose Expedited shipping for delivery within 3-8 business days. We can ship to PO Box address in US. In some instances, subjects such as Management, Accounting, Finance may have different end chapter case studies and exercises. International Edition Textbooks may bear a label ""Not for sale in the U.S. or Canada"" and ""Content may different from U.S. Edition"" - printed only to discourage U.S. students from obtaining an affordable copy. The U.S. Supreme Court has asserted your right to purchase international editions, and ruled on this issue. Access code/CD is not provided with these editions , unless specified. We may ship the books from multiple warehouses across the globe, including India depending upon the availability of inventory storage. Customer satisfaction guaranteed. Seller Inventory # UP_9789332549777

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Paperback
Quantity Available: 15

Seller:

Rating

**Book Description **Paperback. Condition: NEW. This is an International Edition. Brand New Paperback- Same Title Author and Edition as listed. ISBN and Cover design differs. Similar Contents as U.S Edition. Delivery within 3-7 business days ACROSS THE GLOBE. We can ship to PO Box address in US. International Edition Textbooks may bear a label "Not for sale in the U.S. or Canada" or "For sale in Asia only" or similar restrictions- printed only to discourage students from obtaining an affordable copy. US Court has asserted your right to buy and use International edition. Access code/CD may not provided with these editions. We may ship the books from multiple warehouses across the globe including Asia depending upon the availability of inventory. Printed in English. Customer satisfaction guaranteed. Choose expedited shipping for Express delivery. Tracking number provided for every order. Seller Inventory # UB_9789332549777

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Softcover
Quantity Available: > 20

Seller:

Rating

**Book Description **Softcover. Condition: New. 3rd edition. Brand NEW, Paperback International Edition. Black & White or color, Cover and ISBN may be different but similar contents as US editions. Standard delivery takes 5-9 business days by USPS/DHL with tracking number. Choose expedited shipping for superfast delivery 3-5 business days by UPS/DHL/FEDEX. We also ship to PO Box addresses but by Standard delivery and shipping charges will be extra. International Edition Textbooks may bear a label -Not for sale in the U.S. or Canada- etc. printed only to discourage U.S. students from obtaining an affordable copy. Legal to use despite any disclaimer on cover as per US court. No access code or CD included unless specified. In some instances, the international textbooks may have different exercises at the end of the chapters. Printed in English. We may ship the books from multiple warehouses across the globe, including India depending upon the availability of inventory storage. In case of orders from Europe, custom charges may comply by the relevant government authority and we are not liable for it. 100% Customer satisfaction guaranteed! Please feel free to contact us for any queries. Seller Inventory # AB_US_127479

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
PB
Quantity Available: 5

Seller:

Rating

**Book Description **PB. Condition: Brand New. INTERNATIONAL EDITION, Brand New,Softcover,International Edition,Cover & ISBN may be different from US edition. But Contents are same as US Edition.Printed in English Language, Shipped for UPS,DHL,Fedex. Satisfaction Guaranteed. INTERNATIONAL EDITION. Seller Inventory # MK123509

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Paperback
Quantity Available: 10

Seller:

Rating

**Book Description **Paperback. Condition: NEW. This is an International Edition Brand New Paperback Same Title Author and Edition as listed. ISBN and Cover design differs. Similar Contents as U.S Edition. Get free upgrade to Expedited Shipping via DHL Express /Aramex /Fedex on order of more than 3 items.No P.O Box, APO, FPO address. International Edition Textbooks may bear a label "Not for sale in the U.S. or Canada" or "For sale in Asia only" or similar restrictions- printed only to discourage students from obtaining an affordable copy. US Court has asserted your right to buy and use International edition. Access code/CD may not provided with these editions. We may ship the books from multiple warehouses across the globe including Asia depending upon the availability of inventory. Printed in English. Please choose Expedited Shipping for faster Delivery. Customer satisfaction guaranteed. Seller Inventory # U_9789332549777

Published by
Prentice Hall

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Hardcover
Quantity Available: 10

Seller:

Rating

**Book Description **Prentice Hall. Hardcover. Condition: New. 0131679953 Brand New ,International Edition ,Paperback , Same content as U.S edition ,Different ISBN & Cover , we ship from UK , EU ,fast delivery wordwide ( 5-8 business days ). Seller Inventory # IN121N720

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
PAPERBACK
Quantity Available: 10

Seller:

Rating

**Book Description **PAPERBACK. Condition: New. PAPERBACK INTERNATIONAL EDITION Brand New Book. We ship from India. The ISBN-13 or Cover might be different but content is extactly same. We deliver in 5 - 9days and respond quickly to customer queries. Seller Inventory # 0131679953-ABab

Published by
Prentice Hall

ISBN 10: 0131679953
ISBN 13: 9780131679955

New
Hardcover
Quantity Available: 10

Seller:

Rating

**Book Description **Prentice Hall. Hardcover. Condition: New. 0131679953 New ,Paperback , International Edition , Same text as US edition ,Different ISBN /Cover , printed in english , Ready to ship, fast delivery (5-8 busienss days ) worldwide. Seller Inventory # INAM29Y725