Textbook in PDF format

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. Mathematical Models. Elementary Concepts of Graph Theory. Transportation Problems. Connection Problems. Party Problems. Games and Puzzles. Digraphs and Mathematical Models. Graphs and Social Psychology. Planar Graphs and Coloring Problems. Graphs and Other Mathematics. A. Sets, Relations, Functions, and Proofs. Answers, Hints, and Solutions to Selected Exercises