Contents xiii Properties of Trees 414 Leaves 416 Spanning Trees 418 Recap 419 Exercises 420 50 Eulerian Graphs 421 Necessary Conditions 422 Main Theorems 423 Unfinished Business 425 Recap 426 Exercises 426 51 Coloring 427 Core Concepts 427 Bipartite Graphs 429 The Ease of Two-Coloring and the Difficulty of Three-Coloring 433 Recap 434 Exercises 434 52 Planar Graphs 435 Dangerous Curves 435 Embedding 436 Euler's Formula 437 Nonplanar Graphs 440 Coloring Planar Graphs 442 Recap 444 Exercises 444 Chapter 9 Self Test 446 10 Partially Ordered Sets 449 53 Fundamentals of Partially Ordered Sets 449 What Is a Poset? 449 Notation and Language 452 Recap 454 Exercises .454 54 Max and Min 455 Recap 457 Exercises 457 55 Linear Orders 458 Recap 460 Exercises 461
10 Properties of Trees 414 Leaves 416 Spanning Trees 418 Recap 419 Exercises 420 50 Eulerian Graphs Necessary Conditions 421 422 Main Theorems 423 Unfinished Business. 425 Recap 426 Exercises 426 51 Coloring 427 Core Concepts 427 Bipartite Graphs 429 The Ease of Two-Coloring and the Difficulty of Three-Coloring 433 Recap 434 Exercises 434 52 Planar Graphs 435 Dangerous Curves 435 Embedding 436 Euler's Formula 437 Nonplanar Graphs 440 Coloring Planar Graphs 442 Recap 444 Exercises 444 Chapter 9 Self Test 446 Partially Ordered Sets 449 53 Fundamentals of Partially Ordered Sets 449 What Is a Poset? 449 Notation and Language 452 Recap 454 Exercises 454 54 Max and Min 455 Recap 457 Exercises 457 55 Linear Orders 458 Recap 460 Exercises 461 Contents xiii
Xiv Contents 56 Linear Extensions 461 Sorting 465 Linear Extensions of Infinite Posets 467 Recap 468 Exercises 468 57 Dimension 469 Realizers 469 Dimension 471 Embedding 473 Recap 476 Exercises 476 58 Lattices 477 Meet and Join 477 Lattices 479 Recap 481 Exercises 482 Chapter 10 Self Test 483 Appendices 487 A Lots of Hints and Comments;Some Answers 487 B Solutions to Self Tests 515 Chapter 1 515 Chapter 2 516 Chapter 3 518 Chapter 4 520 Chapter 5 524 Chapter 6 526 Chapter 7 530 Chapter 8 532 Chapter 9 535 Chapter 10 539 C Glossary 544 D Fundamentals 552 Numbers 552 Operations 552 Ordering 553 Complex Numbers 553 Substitution 553 Index 555
xiv Contents 56 Linear Extensions 461 Sorting 465 Linear Extensions of Infinite Posets 467 Recap 468 Exercises 468 57 Dimension 469 Realizers 469 Dimension 4 71 Embedding 473 Recap 476 Exercises 4 7 6 58 Lattices 477 Meet and Join 4 77 Lattices 4 79 Recap 481 Exercises 482 Chapter 10 Self Test 483 Appendices 487 A Lots of Hints and Comments; Some Answers 487 8 Solutions to Self Tests 515 Chapter 1 515 Chapter 2 516 Chapter 3 518 Chapter 4 520 Chapter 5 524 Chapter 6 526 Chapter 7 530 Chapter 8 532 Chapter 9 535 Chapter 10 539 c Glossary 544 D Fundamentals 552 Numbers 552 Operations 552 Ordering 553 Complex Numbers 553 Substitution 553 Index 555
To the Student Welcome. This book is an introduction to mathematics.In particular,it is an introduction to discrete mathematics.What do these terms-discrete and mathematics-mean? Continuous versus discrete The world of mathematics can be divided roughly into two realms:the con- mathematics tinuous and the discrete.The difference is illustrated nicely by wristwatches. Continuous mathematics corresponds to analog watches-the kind with separate hour,minute,and second hands.The hands move smoothly over time.From an ana- log watch perspective,between 12:02 P.M.and 12:03 P.M.there are infinitely many possible different times as the second hand sweeps around the watch face.Contin- uous mathematics studies concepts that are infinite in scope,in which one object blends smoothly into the next.The real-number system lies at the core of con- tinuous mathematics,and-just as on the watch-between any two real numbers, there is an infinity of real numbers.Continuous mathematics provides excellent models and tools for analyzing real-word phenomena that change smoothly over time,including the motion of planets around the sun and the flow of blood through the body. Discrete mathematics,on the other hand,is comparable to a digital watch. On a digital watch there are only finitely many possible different times between 12:02 P.M.and 12:03 P.M.A digital watch does not acknowledge split seconds! There is no time between 12:02:03 and 12:02:04.The watch leaps from one time to the next.A digital watch can show only finitely many different times,and the transition from one time to the next is sharp and unambiguous.Just as the real numbers play a central role in continuous mathematics,integers are the primary tool of discrete mathematics.Discrete mathematics provides excellent models and tools for analyzing real-world phenomena that change abruptly and that lie clearly in one state or another.Discrete mathematics is the tool of choice in a host of applications,from computers to telephone call routing and from personnel assignments to genetics. What is mathematics？A Let us turn to a harder question:What is mathematics?A reasonable answer more sophisticated answer is that mathematics is the study of numbers and shapes.The particular word in is that mathematics is the this definition we would like to clarify is study.How do mathematicians approach study of sets,functions, and concepts built on these their work? fundamental notions. Every field has its own criteria for success.In medicine,success is healing and the relief of suffering.In science,the success of a theory is determined through experimentation.Success in art is the creation of beauty.Lawyers are successful when they argue cases before juries and convince the jurors of their clients'cases. Players in professional sports are judged by whether they win or lose.And success in business is profit. XV
Continuous versus discrete mathematics. What is mathematics? A more sophisticated answer is that mathematics is the study of sets, functions, and concepts built on these fundamental notions. To the Student Welcome. This book is an introduction to mathematics, In particular, it is an introduction to discrete mathematics. What do these terms-discrete and mathematics-mean? The world of mathematics can be divided roughly into two realms: the continuous and the discrete. The difference is illustrated nicely by wristwatches. Continuous mathematics corresponds to analog watches-the kind with separate hour, minute, and second hands. The hands move smoothly over time. From an analog watch perspective, between 12:02 P.M. and 12:03 P.M. there are infinitely many possible different times as the second hand sweeps around the watch face. Continuous mathematics studies concepts that are infinite in scope, in which one object blends smoothly into the next. The real-number system lies at the core of continuous mathematics, and-just as on the watch-between any two real numbers, there is an infinity of real numbers. Continuous mathematics provides excellent models and tools for analyzing real-word phenomena that change smoothly over time, including the motion of planets around the sun and the flow of blood through the body. Discrete mathematics, on the other hand, is comparable to a digital watch. On a digital watch there are only finitely many possible different times between 12:02 P.M. and 12:03 P.M. A digital watch does not acknowledge split seconds! There is no time between 12:02:03 and 12:02:04. The watch leaps from one time to the next. A digital watch can show only finitely many different times, and the transition from one time to the next is sharp and unambiguous. Just as the real numbers play a central role in continuous mathematics, integers are the primary tool of discrete mathematics. Discrete mathematics provides excellent models and tools for analyzing real-world phenomena that change abruptly and that lie clearly in one state or another. Discrete mathematics is the tool of choice in a host of applications, from computers to telephone call routing and from personnel assignments to genetics. Let us tum to a harder question: What is mathematics? A reasonable answer is that mathematics is the study of numbers and shapes. The particular word in this definition we would like to clarify is study. How do mathematicians approach their work? Every field has its own criteria for success. In medicine, success is healing and the relief of suffering. In science, the success of a theory is determined through experimentation. Success in art is the creation of beauty. Lawyers are successful when they argue cases before juries and convince the jurors of their clients' cases. Players in professional sports are judged by whether they win or lose. And success in business is profit. XV
xvi To the Student What is successful mathematics?Many people lump mathematics together with science.This is plausible,because mathematics is incredibly useful for science,but of the various fields just described,mathematics has less to do with science than it does with law and art! Mathematical success is measured by proof.A proof is an essay in which an assertion,such as"There are infinitely many prime numbers,"is incontrovertibly shown to be correct.Mathematical statements and proofs are,first and foremost, judged in terms of their correctness.Other,secondary criteria are also important. Mathematicians are concerned with creating beautiful mathematics.And mathe- matics is often judged in terms of its utility;mathematical concepts and techniques are enormously useful in solving real-world problems. Proof writing. One of the principal aims of this book is to teach you,the student,how to write proofs.Long after you complete this course in discrete mathematics,you may find that you do not need to know how many k-element subsets an n-element set has or how Fermat's Little Theorem can be used as a test for primality.Proof writing,by contrast,will always serve you well.It trains us to think clearly and present our case logically. Many students find proof writing frightening and difficult.They might freeze after writing the word proof on their paper,unsure what to do next.The anti- dote to this proof phobia can be found in the pages of this book!We demystify the proof-writing process by decoding the idiosyncrasies of mathematical English Proof【emplates. and by providing proof templates.The proof templates,scattered throughout this book,provide the structure (and boilerplate language)for the most common vari- eties of mathematical proofs.Do you need to prove that two sets are equal?See Proof Template 5!Trying to show that a function is one-to-one?Consult Proof Template 20! How to Read a Mathematics Book Reading a mathematics book is an active process.You should have a pad of paper and a pencil handy as you read.Work out the examples and create examples of your own.Before you read the proofs of the theorems in this book,try to write your own proof.Then,if you get stuck,read the proof in the book. One of the marvelous features of mathematics is that you need not(perhaps, should not!)trust the author.If a physics book refers to an experimental result,it might be difficult or prohibitively expensive for you to do the experiment yourself. If a history book describes some events,it might be highly impractical to consult the original sources(which may be in a language you do not understand).But with mathematics,all is before you to verify.Have a reasonable attitude of doubt as you read;demand of yourself to verify the material presented.Mathematics is not so much about the truths it espouses but about how those truths are established.Be an active participant in the process. One way to be an active participant is to work on the hundreds of exercises found in this text.If you run into difficulty,you may be helped by the many hints and occasional answers in Appendix A.However,I hope you will not treat this book as just a collection of problems with some stuff thrown in to keep the publisher happy.I tried hard to make the exposition clear and useful to students.If you find it
xvi To the Student What is successful mathematics? Many people lump mathematics together with science. This is plausible, because mathematics is fncredibly useful for science, but of the various fields just described, mathematics has less to do with science than it does with law and art! Mathematical success is measured by proof A proof is an essay in which an assertion, such as "There are infinitely many prime numbers," is incontrovertibly shown to be correct. Mathematical statements and proofs are, first and foremost, judged in terms of their correctness. Other, secondary criteria are also important. Mathematicians are concerned with creating beautiful mathematics. And mathematics is often judged in terms of its utility; mathematical concepts and techniques are enormously useful in solving real-world problems. Proof writing. One of the principal aims of this book is to teach you, the student, how to write proofs. Long after you complete this course in discrete mathematics, you may find that you do not need to know how many k-element subsets ann-element set has or how Fermat's Little Theorem can be used as a test for primality. Proof writing, by contrast, will always serve you well. It trains us to think clearly and present our case logically. Many students find proof writing frightening and difficult. They might freeze after writing the word proof on their paper, unsure what to do next. The antidote to this proof phobia can be found in the pages of this book! We demystify the proof-writing process by decoding the idiosyncrasies of mathematical English Proof templates. and by providing proof templates. The proof templates, scattered throughout this book, provide the structure (and boilerplate language) for the most common varieties of mathematical proofs. Do you need to prove that two sets are equal? See Proof Template 5! Trying to show that a function is one-to-one? Consult Proof Template 20! How to Read a Mathematics Book Reading a mathematics book is an active process. You should have a pad of paper and a pencil handy as you read. Work out the examples and create examples of your own. Before you read the proofs of the theorems in this book, try to write your own proof. Then, if you get stuck, read the proof in the book. One of the marvelous features of mathematics is that you need not (perhaps, should not!) trust the author. If a physics book refers to an experimental result, it might be difficult or prohibitively expensive for you to do the experiment yourself. If a history book describes some events, it might be highly impractical to consult the original sources (which may be in a language you do not understand). But with mathematics, all is before you to verify. Have a reasonable attitude of doubt as you read; demand of yourself to verify the material presented. Mathematics is not so much about the truths it espouses but about how those truths are established. Be an active participant in the process. One way to be an active participant is to work on the hundreds of exercises found in this text. If you run into difficulty, you may be helped by the many hints and occasional answers in Appendix A. However, I hope you will not treat this book as just a collection of problems with some stuff thrown in to keep the publisher happy. I tried hard to make the exposition clear and useful to students. If you find it
To the Student xvii otherwise,please let me know.I hope to improve this book continually,so send your comments to me by email at ers@jhu.edu or by conventional letter to Professor Edward Scheinerman,Department of Applied Mathematics and Statistics,The Johns Hopkins University,Baltimore,Maryland 21218,USA.Thank you. I hope you enjoy. Exercises 1.On a digital watch there are only finitely many different times that can be displayed.How many different times can be displayed on a digital watch that shows hours,minutes,and seconds and that distinguishes between A.M.and PM.？ 2.An ice cream shop sells ten different flavors of ice cream.You order a two- scoop sundae.In how many ways can you choose the flavors for the sundae if the two scoops in the sundae are different flavors?
Exercises To the Student xvii otherwise, please let me know. I hope to improve this book continually, so send your comments to me by email at ers@jhu. edu or by conventional letter to Professor Edward Scheinerman, Department of Applied Mathematics and Statistics, The Johns Hopkins University, Baltimore, Maryland 21218, USA. Thank you. I hope you enjoy. 1. On a digital watch there are only finitely many different times that can be displayed. How many different times can be displayed on a digital watch that shows hours, minutes, and seconds and that distinguishes between A.M. and P.M.? 2. An ice cream shop sells ten different flavors of ice cream. You order a twoscoop sundae. In how many ways can you choose the flavors for the sundae if the two scoops in the sundae are different flavors?