COMBINATORICS

1 P1: FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 1, 201112:27iiThis page is intentionally left : FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 1, 201112:27 APPLIEDCOMBINATORICSiP1: FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 1, 201112:27iiThis page is intentionally left : FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 28, 20118:0 APPLIEDCOMBINATORICSALAN TUCKERSUNY Stony BrookJohn Wiley & Sons, : FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerDecember 1, 201116:7VP AND PUBLISHERL aurie RosatonePROJECT EDITORS hannon CorlissMARKETING MANAGERDebi DoyleMARKETING ASSISTANTP atrick FlatleyPRODUCTION MANAGERJ anis SooASSISTANT PRODUCTION EDITORE laine S.

2 ChewCOVER ILLUSTRATOR & DESIGNERSeng Ping NgiengThis book was set in Times by Aptara, Inc. and printed and bound by Courier Westford, Inc. The coverwas printed by Courier Westford, book is printed on acid free paper. Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding formore than 200 years, helping people around the world meet their needs and fulfill their aspirations. Ourcompany is built on a foundation of principles that include responsibility to the communities we serveand where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort toaddress the environmental, social, economic, and ethical challenges we face in our business. Among theissues we are addressing are carbon impact, paper specifications and procurement, ethical conduct withinour business and among our vendors, and community and charitable support.

3 For more information,please visit our website: 2012, 2007, 2002, 1995 John Wiley & Sons, Inc. All rights reserved. No part of thispublication may be reproduced, stored in a retrieval system or transmitted in any form or by any means,electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted underSections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permissionof the Publisher, or authorization through payment of the appropriate per-copy fee to the CopyrightClearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, website to the Publisher for permission should be addressed to the Permissions Department, John Wiley& Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201)748-6011, fax (201)748-6008, copies are provided to qualified academics and professionals for review purposes only, for usein their courses during the next academic year.

4 These copies are licensed and may not be sold ortransferred to a third party. Upon completion of the review period, please return the evaluation copyto Wiley. Return instructions and a free of charge return mailing label are available If you have chosen to adopt this textbook for use in your course, pleaseaccept this book as your complimentary desk copy. Outside of the United States, please contact yourlocal sales of Congress Cataloging-in-Publication DataTucker, Alan, 1943 July 6-Applied COMBINATORICS / Alan Tucker. 6th bibliographical references and 978-0-470-45838-9 (acid free paper)1. Combinatorial analysis. 2. Graph theory. I. 2012511 .6 dc232011044318 Printed in the United States of : FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 28, 20118:0 PREFACEC ombinatorial reasoning underlies all analysis of computer systems.

5 It plays asimilar role in discrete operations research problems and in finite probability. Twoof the most basic mathematical aspects of computer science concern the speed andlogical structure of a computer program. Speed involves enumeration of the numberof times each step in a program can be performed. Logical structure involves flowcharts, a form of graphs. Analysis of the speed and logical structure of operationsresearch algorithms to optimize efficient manufacturing or garbage collection entailssimilar combinatorial mathematics. Determining the probability that one of a certainsubset of equally likely outcomes occurs requires counting the size of the combinatorial probability is the basis of many nonparametric statistical , enumeration and graph theory are used pervasively throughout the book teaches students how to reason and model combinatorially.

6 It seeks todevelop proficiency in basic discrete math problem solving in the way that a calculustextbook develops proficiency in basic analysis problem three principal aspects of combinatorial reasoning emphasized in this bookare the systematic analysis of different possibilities, the exploration of the logicalstructure of a problem ( , finding manageable subpieces or first solving the problemwith three objects instead ofn), and ingenuity. Although important uses of combina-torics in computer science, operations research, and finite probability are mentioned,these applications are often used solely for motivation. Numerical examples involvingthe same concepts use more interesting settings such as poker probabilities or is always first motivated by examples, and proofs are given only whentheir reasoning is needed to solve applied problems.

7 Elsewhere, results are statedwithout proof, such as the form of solutions to various recurrence relations, and thenapplied in problem solving. Occasionally, a few theorems are stated simply to givestudents a flavor of what the theory in certain areas is decades, collegiate curriculum recommendations from the MathematicalAssociation of America have included combinatorial problem solving as an impor-tant component of training in the mathematical sciences. Combinatorial problemsolving underlies a wide spectrum of important subjects in the computer sciencecurriculum. Indeed, it is expected that most students in a course using this book will becomputer science majors. For both mathematics majors and computer science majors,vP1: FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 1, 201112:27viPrefacethis author believes that general reasoning skills stressed here are more important thanmastering a variety of definitions and book is designed for use by students with a wide range of ability and maturity(sophomores through beginning graduate students).

8 The stronger the students, theharder the exercises that can be assigned. The book can be used for a one-quarter,two-quarter, or one-semester course depending on how much material is used. It mayalso be used for a one-quarter course in applied graph theory or a one-semester orone-quarter course in enumerative COMBINATORICS (starting from Chapter 5). A typicalone-semester undergraduate discrete methods course should cover most of Chapters1 to 3 and 5 to 8, with selected topics from other chapters if time are strongly encouraged to obtain a copy of the instructor s guideaccompanying this guide has an extensive discussion of common studentmisconceptions about particular topics, hints about successful teaching styles for thiscourse, and sample course outlines (weekly assignments, tests, etc.)

9 The sixth edition of this book draws upon features from all the earlier example, the game of Mastermind that appeared at the beginning of the firstedition has been brought back, and a closing Postlude about cryptanalysis has beenadded. The suggested solutions to selected enumeration exercises from the secondand third editions have returned. Of course, there are also new exercises. Also, thenumbers were changed in many of the old exercises in the counting chapters (to guardagainst student groups accumulating old solution sets).Many people gave useful comments about early drafts and the first edition ofthis text; Jim Frauenthal and Doug West were especially helpful. The idea for thisbook is traceable to a COMBINATORICS course taught by George Dantzig and GeorgePolya at Stanford in 1969, a course for which I was the grader.

10 Many instructorswho have used earlier editions of this book have supplied me with valuable feedbackand suggestions that have, I hope, made this edition better. I gratefully acknowledgemy debt to them. Ultimately, my interest in combinatorial mathematics and in itseffective teaching rests squarely on the shoulders of my father, A. W. Tucker, whohad long sought to give finite mathematics a greater role in mathematics as well asin the undergraduate mathematics curriculum. Finally, special thanks go to formerstudents of my combinatorial mathematics courses at Stony Brook. It wastheywhotaughtmehow to teach this TuckerStony Brook, New : FCH/FYXP2: FCH/FYXQC: FCH/UKST1: FCHF rontmatterWB00623-TuckerNovember 28, 20118:0 CONTENTSPRELUDExiPART ONE GRAPH THEORY1 CHAPTER 1 ELEMENTS OF GRAPH Graph Models Isomorphism Edge Counting Planar Graphs Summary and References 44 Supplementary Exercises45 CHAPTER 2 COVERING CIRCUITS ANDGRAPH Euler Cycles Hamilton Circuits Graph Coloring Coloring Theorems Summary and References 86 Supplement: Graph Model for Instant Insanity87 Supplement Exercises92 CHAPTER 3 TREES AND Properties of Trees Search Trees and Spanning Trees The Traveling Salesperson Problem 113viiP1: FCH/FYXP2.