Discrete Mathematics With Graph Theory 3rd Edition.pdf
Kasey Finkenbinder
used to express the negation of any symbol over which it is written;for example, , means "does not belong to"used to denote the end of a proofthe absolute value of xpronounced "aleph naught," this is the cardinality of the naturalnumbersapproximatelysumproduct
Acquisitions Editor: George LobellProduction Editor/Assistant Managing Editor: Bayani Mendoza de LeonVice-President/Director of Production and Manufacturing: David W. RiccardiExecutive Managing Editor: Kathleen SchiaparelliSenior Managing Editor: Linda Mihatov BehrensManufacturing Buyer: Alan FischerManufacturing Manager: Trudy PisciottiMarketing Manager: Angela BattleAssistant Editor of Media: Vince JansenManaging Editor, Audio/Video Assets: Grace HazeldineCreative Director: Carole AnsonPaul Belfanti: Director of Creative ServicesInterior/Cover Designer: John ChristianaArt Director: Maureen EideEditorial Assistant: Melanie Van BenthuysenCover Image: Wassily Kandinsky, "Entwurf zu Kreise im Kreis" 1923, Philadelphia Museum of Art/
Pearson Education Ltd., LondonPearson Education Australia Pty. Limited, SydneyPearson Education Singapore, Pte. Ltd.Pearson Education North Asia Ltd., Hong KongPearson Education Canada, Ltd., TorontoPearson EducaciUn de Mexico, S.A. de C.V.Pearson Education - Japan, TokyoPearson Education Malaysia, Pte. Ltd.
Only those who live with an author can appreciate the work that goesinto writing. We are sincerely grateful for the loving encouragementand patience of our wives over a period of years while we have workedon two editions of this book.
Few people ever read a preface, and those who do often just glance at the first few lines. So webegin by answering the question most frequently asked by the readers of our manuscript: "Whatdoes [BB] mean?" Like most undergraduate texts in mathematics these days, answers to someof our exercises appear at the back of the book. Those which do are marked [BB] for "Back ofBook." In this book, complete solutions, not simply answers, are given to almost all the exercisesmarked [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 thatour enthusiasm for mathematics and, in particular, for discrete mathematics is transmitted to ourreaders 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 domainthe natural numbers that are often studied. Perhaps the best way to summarize the subject matterof this book is to say that discrete mathematics is the study of problems associated with thenatural numbers.
You should never read a mathematics book or notes taken in a mathematics course the wayyou read a novel, in an easy chair by the fire. You should read at a desk, with paper and pencilat hand, verifying statements which are less than clear and inserting question marks in marginsso that you are ready to ask questions at the next available opportunity.
Definitions and terminology are terribly important in mathematics, much more so than manystudents 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 bookcontains a glossary of definitions (often including examples) at the end as well as a summary ofnotation 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 amoment" and think about a specific point we have just raised. Our Pauses are little questionsintended to be solved on the spot, right where they occur, like this.
The answers to Pauses are given at the end of every section just before the exercises. So whena 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!
Discrete mathematics is quite different from other areas in mathematics which you may havealready studied, such as algebra, geometry, or calculus. It is much less structured; there are farfewer standard techniques to learn. It is, however, a rich subject full of ideas at least some ofwhich we hope will intrigue you to the extent that you will want to learn more about them. Relatedsources of material for further reading are given in numerous footnotes throughout the text.
I am a student at Memorial University of Newfoundland and have taken a course based on apreliminary version of this book. I spent one summer working for the authors, helping them totry to improve the book. As part of my work, they asked me to write an introduction for thestudent. They felt a fellow student would be the ideal person to prepare (warn?) other studentsbefore they got too deeply engrossed in the book.
There are many things which can be said about this textbook. The authors have a unique senseof humor, which often, subtly or overtly, plays a part in their presentation of material. It is aneffective tool in keeping the information interesting and, in the more subtle cases, in keepingyou alert. They try to make discrete mathematics as much fun as possible, at the same timemaximizing the information presented.
While the authors do push a lot of new ideas at you, they also try hard to minimize potentialdifficulties. This is not an easy task considering that there are many levels of students who willuse 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 theharder ones near the end.
Concerning the exercises, the authors' primary objective is not to stump you or to test morethan you should know. The purpose of the exercises is to help clarify the material and to makesure you understand what has been covered. The authors intend that you stop and think beforeyou start writing.
Inevitably, not everything in this book is exciting. Some material may not even seem par-ticularly useful. As a textbook used for discrete mathematics and graph theory, there are manytopics which must be covered. Generally, less exciting material is in the first few chapters andmore interesting topics are introduced later. For example, the chapter on sets and relations maynot 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 asubsequent 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 tobegin to think seriously about various areas of modern mathematics. The best way to approachthis book is with pencil, paper, and an open mind.
To the InstructorSince the first printing of this book, we have received a number of queries about the existence ofa solutions manual. Let us begin then with the assurance that a complete solutions manual doesexist 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-semestercourses, one in discrete mathematics at the sophomore level (with no graph theory) and the otherin applied graph theory (at the junior level). We believe this book is more elementary and writtenwith a far more leisurely style than comparable books on the market. For example, since studentscan enter our courses without calculus or without linear algebra, this book does not presume thatstudents have backgrounds in either subject. The few places where some knowledge of a firstcalculus or linear algebra course would be useful are clearly marked. With one exception, thisbook requires virtually no background. The exception is Section 10.3, on the adjacency matrixof a graph, where we assume a little linear algebra. If desired, this section can easily be omittedwithout consequences.
The material for our first course can be found in Chapters 1 through 7, although we find itimpossible to cover all the topics presented here in the thirty-three 50-minute lectures availableto us. There are various ways to shorten the course. One possibility is to omit Chapter 4 (TheIntegers), although it is one of our favorites, especially if students will subsequently take anumber theory course. Another solution is to omit all but the material on mathematical inductionin Chapter 5, as well as certain other individual topics, such as partial orders (Section 2.5) andderangements (Section 7.4).
Graph theory is the subject of Chapters 9 through 15, and again we find that there is morematerial here than can be successfully treated in thirty-three lectures. Usually, we include only aselection of the various applications and algorithms presented in this part of the text. We do notalways discuss the puzzles in Section 9. 1, scheduling problems (Section 11.5), applications of theMax Flow-Min Cut Theorem, or matchings (Sections 15.3 and 15.4). Chapter 13 (Depth-FirstSearch and Applications) can also be omitted without difficulty. In fact, most of the last half ofthis book is self-contained and can be treated to whatever extent the instructor may desire.
Wherever possible, we have tried to keep the material in various chapters independent of mate-rial 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 readingabout congruence in Section 4.4, and one must study Hamiltonian graphs (Section 10.2) beforelearning about facilities design in Section 14.3. For the most part, however, the graph theorymaterial can be read independently of earlier chapters. Some knowledge of such basic notions asfunction (Chapter 3) and equivalence relation is needed in several places and, of course, manyproofs in graph theory require mathematical induction (Section 5.1).
b1e95dc632