Contents xvii Matching in Bipartite Graphs 417 Searching for Augmenting Paths in Bipartite Graphs 417 The Augmentation-Cover Algorithm 420 Efficient Algorithms 426 Important Concepts,Formulas,and Theorems 427 Problems 428 6.5 Coloring and Planarity 430 The Idea of Coloring 430 Interval Graphs 433 Planarity 435 The Faces of a Planar Drawing 437 The Five-Color Theorem 441 Important Concepts,Formulas,and Theorems 444 Problems 445 APPENDIX A Derivation of the More General Master Theorem 449 More General Recurrences 449 Recurrences for General n 451 Removing Floors and Ceilings 452 Floors and Ceilings in the Stronger Version of the Master Theorem 453 Proofs of Theorems 453 Important Concepts,Formulas,and Theorems 457 Problems 458 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479Contents xvii Matching in Bipartite Graphs 417 Searching for Augmenting Paths in Bipartite Graphs 417 The Augmentation-Cover Algorithm 420 Efficient Algorithms 426 Important Concepts, Formulas, and Theorems 427 Problems 428 6.5 Coloring and Planarity 430 The Idea of Coloring 430 Interval Graphs 433 Planarity 435 The Faces of a Planar Drawing 437 The Five-Color Theorem 441 Important Concepts, Formulas, and Theorems 444 Problems 445 APPENDIX A Derivation of the More General Master Theorem 449 More General Recurrences 449 Recurrences for General n 451 Removing Floors and Ceilings 452 Floors and Ceilings in the Stronger Version of the Master Theorem 453 Proofs of Theorems 453 Important Concepts, Formulas, and Theorems 457 Problems 458 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479