Undergraduate Texts in Mathematics - Lagout.org

1 Undergraduate Texts in MathematicsEditorsS. RibetFor other titles published in this series, go M. Harris Jeffry L. Hirst Michael J. MossinghoffCombinatorics andGraph TheorySecond Edition123 John M. HarrisJeffry L. HirstDepartment of MathematicsMathematical SciencesFurman UniversityAppalachian State UniversityGreenville, SC 29613121 Bodenheimer , NC J. MossinghoffDepartment of MathematicsDavidson CollegeBox 6996 Davidson, NC BoardS. RibetMathematics DepartmentDepartment of MathematicsSan Francisco State UniversityUniversity of CaliforniaSan Francisco, CA 94132at BerkeleyUSAB erkeley, CA 0172-6056 ISBN: 978-0-387-797710-6e-ISBN: 978-0-387-79711-3 DOI: of Congress Control Number: 2008934034 Mathematics Subject Classification (2000): 05-01 03-01c 2008 Springer Science+Business Media, LLCAll rights reserved.

2 This work may not be translated or copied in whole or in part without the writtenpermission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Usein connection with any form of information storage and retrieval, electronic adaptation, computersoftware, or by similar or dissimilar methodologynow known or hereafter developed is use in this publication of trade names, trademarks, service marks, and similar terms, even if theyare not identified as such, is not to be taken as an expression of opinion as to whether or not they aresubject to proprietary on acid-free , Sophie, and Will,Holly,Kristine, Amanda.

3 And AlexandraPreface to the Second EditionThere are certain rules that one must abide by in order to create asuccessful sequel. Randy Meeks, from the trailer toScream 2 While we may not follow the precise rules that Mr. Meeks had in mind for suc-cessful sequels, we have made a number of changes to the text in this secondedition. In the new edition, we continue to introduce new topics with concrete ex-amples, we provide complete proofs of almost every result, and we preserve thebook s friendly style and lively presentation, interspersing the text with occasionaljokes and quotations. The first two chapters, on graph theory and combinatorics,remain largely independent, and may be covered in either order.

4 Chapter 3, oninfinite combinatorics and graphs, may also be studied independently, althoughmany readers will want to investigate trees, matchings, and Ramsey theory forfinite sets before exploring these topics for infinite sets in the third chapter. Likethe first edition, this text is aimed at upper-division Undergraduate students inmathematics, though others will find much of interest as well. It assumes onlyfamiliarity with basic proof techniques, and some experience with matrices andinfinite second edition offers many additional topics for use in the classroom or forindependent study. Chapter 1 includes a new section covering distance and relatednotions in graphs, following an expanded introductory section.

5 This new sectionalso introduces the adjacency matrix of a graph, and describes its connection toimportant features of the graph. Another new section on trails, circuits, paths,and cycles treats several problems regarding Hamiltonian and Eulerian paths inviiiPreface to the Second Editiongraphs, and describes some elementaryopen problems regarding paths in graphs,and graphs with forbidden topics were added to Chapter 2. The introductory section on basiccounting principles has been expanded. Early in the chapter, a new section coversmultinomial coefficients and their properties, following the development of thebinomial coefficients.

6 Another new section treats the pigeonhole principle, withapplications to some problems in number theory. The material on P olya s theoryof counting has now been expanded to cover de Bruijn s more general method ofcounting arrangements in the presence of one symmetry group acting on the ob-jects, and another acting on the set of allowed colors. A new section has also beenadded on partitions, and the treatment of Eulerian numbers has been significantlyexpanded. The topic of stable marriage is developed further as well, with threeinteresting variations on the basic problem now covered here. Finally, the endof the chapter features a new section on combinatorial geometry.

7 Two principalproblems serve to introduce this rich area: a nice problem of Sylvester s regard-ing lines produced by a set of points in the plane, and the beautiful geometricapproach to Ramsey theory pioneered by Erd os and Szekeres in a problem aboutthe existence of convex polygons among finite sets of points in the Chapter 3, a new section develops the theory of matchings further by in-vestigating marriage problems on infinite sets, both countable and new section toward the end of this chapter describes a characterizationof certain large infinite cardinals by using linear orderings. Many new exerciseshave also been added in each chapter,and the list of references has been com-pletely second edition grew out of our experiences teaching courses in graph the-ory, combinatorics, and set theory at Appalachian State University, Davidson Col-lege, and Furman University, and we thank these institutions for their support, andour students for their comments.

8 We also thank Mark Spencer at , we thank our families for their patience and constant good humor through-out this process. The first and third authors would also like to add that, since theoriginal publication of this book, their families have both gained their own secondadditions!May 2008 John M. HarrisJeffry L. HirstMichael J. MossinghoffPreface to the First EditionThree things should be considered: problems, theorems, andapplications. Gottfried Wilhelm Leibniz,Dissertatio de Arte Combinatoria, 1666 This book grew out of several courses in combinatorics and graph theory given atAppalachian State University and UCLA in recent years.

9 A one-semester coursefor juniors at Appalachian State University focusing on graph theory covered mostof Chapter 1 and the first part of Chapter 2. A one-quarter course at UCLA oncombinatorics for undergraduates concentrated on the topics in Chapter 2 andincluded some parts of Chapter 1. Another semester course at Appalachian Statefor advanced undergraduates and beginninggraduate students covered most of thetopics from all three are rather few prerequisites for this text. We assume some familiaritywith basic proof techniques, like induction. A few topics in Chapter 1 assumesome prior exposure to elementary linear algebra .

10 Chapter 2 assumes some famil-iarity with sequences and series, especially Maclaurin series, at the level typicallycovered in a first-year calculus course. The text requires no prior experience withmore advanced subjects, such as group this book is primarily intended for upper-division Undergraduate stu-dents, we believe that others will find it useful as well. Lower-division undergrad-uates with a penchant for proofs, and even talented high school students, will beable to follow much of the material, and graduate students looking for an intro-duction to topics in graph theory, combinatorics, and set theory may find severaltopics of to the First EditionChapter 1 focuses on the theory of finite graphs.