Introduction to Graph Theory

by West, Douglas B.

• ISBN13: 9780130144003
• ISBN10: 0130144002
• Edition: 2nd
• Format: Hardcover
• Copyright: 2000-08-22
• Publisher: Pearson

Summary

This book fills a need for a thorough introduction to graph theory that features both the understanding and writing of proofs about graphs. Verification that algorithms work is emphasized more than their complexity.An effective use of examples, and huge number of interesting exercises, demonstrate the topics of trees and distance, matchings and factors, connectivity and paths, graph coloring, edges and cycles, and planar graphs.For those who need to learn to make coherent arguments in the fields of mathematics and computer science.

Table of Contents

Preface	xi
Fundamental Concepts	1	(66)
What Is a Graph?	1	(18)
The Definition	1	(2)
Graphs as Models	3	(3)
Matrices and Isomorphism	6	(5)
Decomposition and Special Graphs	11	(3)
Exercises	14	(5)
Paths, Cycles, and Trails	19	(15)
Connection in Graphs	20	(4)
Bipartite Graphs	24	(2)
Eulerian Circuits	26	(5)
Exercises	31	(3)
Vertex Degrees and Counting	34	(19)
Counting and Bijections	35	(3)
Extremal Problems	38	(6)
Graphic Sequences	44	(3)
Exercises	47	(6)
Directed Graphs	53	(14)
Definitions and Examples	53	(5)
Vertex Degrees	58	(2)
Eulerian Digraphs	60	(1)
Orientations and Tournaments	61	(2)
Exercises	63	(4)
Trees and Distance	67	(40)
Basic Properties	67	(14)
Properties of Trees	68	(2)
Distance in Trees and Graphs	70	(3)
Disjoint Spanning Trees (optional)	73	(2)
Exercises	75	(6)
Spanning Trees and Enumeration	81	(14)
Enumeration of Trees	81	(2)
Spanning Trees in Graphs	83	(4)
Decomposition and Graceful Labelings	87	(2)
Branchings and Eulerian Digraphs (optional)	89	(3)
Exercises	92	(3)
Optimization and Trees	95	(12)
Minimum Spanning Tree	95	(2)
Shortest Paths	97	(3)
Trees in Computer Science (optional)	100	(3)
Exercises	103	(4)
Matchings and Factors	107	(42)
Matchings and Covers	107	(16)
Maximum Matchings	108	(2)
Hall's Matching Condition	110	(2)
Min-Max Theorems	112	(1)
Independent Sets and Covers	113	(3)
Dominating Sets (optional)	116	(2)
Exercises	118	(5)
Algorithms and Applications	123	(13)
Maximum Bipartite Matching	123	(2)
Weighted Bipartite Matching	125	(5)
Stable Matchings (optional)	130	(2)
Faster Bipartite Matching (optional)	132	(2)
Exercises	134	(2)
Matchings in General Graphs	136	(13)
Tutte's 1-factor Theorem	136	(4)
f-factors of Graphs (optional)	140	(2)
Edmonds' Blossom Algorithm (optional)	142	(3)
Exercises	145	(4)
Connectivity and Paths	149	(42)
Cuts and Connectivity	149	(12)
Connectivity	149	(3)
Edge-connectivity	152	(3)
Blocks	155	(3)
Exercises	158	(3)
k-connected Graphs	161	(15)
2-connected Graphs	161	(3)
Connectivity of Digraphs	164	(2)
k-connected and k-edge-connected Graphs	166	(4)
Applications of Menger's Theorem	170	(2)
Exercises	172	(4)
Network Flow Problems	176	(15)
Maximum Network Flow	176	(5)
Integral Flows	181	(3)
Supplies and Demands (optional)	184	(4)
Exercises	188	(3)
Coloring of Graphs	191	(42)
Vertex Colorings and Upper Bounds	191	(13)
Definitions and Examples	191	(3)
Upper Bounds	194	(3)
Brooks' Theorem	197	(2)
Exercises	199	(5)
Structure of k-chromatic Graphs	204	(15)
Graphs with Large Chromatic Number	205	(2)
Extremal Problems and Turan's Theorem	207	(3)
Color-Critical Graphs	210	(2)
Forced Subdivisions	212	(2)
Exercises	214	(5)
Enumerative Aspects	219	(14)
Counting Proper Colorings	219	(5)
Chordal Graphs	224	(2)
A Hint of Perfect Graphs	226	(2)
Counting Acyclic Orientations (optional)	228	(1)
Exercises	229	(4)
Planar Graphs	233	(40)
Embeddings and Euler's Formula	233	(13)
Drawings in the Plane	233	(3)
Dual Graphs	236
Euler's Formula	241	(2)
Exercises	243	(3)
Characterization of Planar Graphs	246	(11)
Preparation for Kuratowski's Theorem	247	(1)
Convex Embeddings	248	(4)
Planarity Testing (optional)	252	(3)
Exercises	255	(2)
Parameters of Planarity	257	(16)
Coloring of Planar Graphs	257	(4)
Crossing Number	261	(5)
Surfaces of Higher Genus (optional)	266	(3)
Exercises	269	(4)
Edges and Cycles	273	(46)
Line Graphs and Edge-coloring	273	(13)
Edge-colorings	274	(5)
Characterization of Line Graphs (optional)	279	(3)
Exercises	282	(4)
Hamiltonian Cycles	286	(13)
Necessary Conditions	287	(1)
Sufficient Conditions	288	(5)
Cycles in Directed Graphs (optional)	293	(1)
Exercises	294	(5)
Planarity, Coloring, and Cycles	299	(20)
Tait's Theorem	300	(2)
Grinberg's Theorem	302	(2)
Snarks (optional)	304	(3)
Flows and Cycle Covers (optional)	307	(7)
Exercises	314	(5)
Additional Topics (optional)	319	(152)
Perfect Graphs	319	(30)
The Perfect Graph Theorem	320	(3)
Chordal Graphs Revisited	323	(5)
Other Classes of Perfect Graphs	328	(6)
Imperfect Graphs	334	(6)
The Strong Perfect Graph Conjecture	340	(4)
Exercises	344	(5)
Matroids	349	(29)
Hereditary Systems and Examples	349	(5)
Properties of Matroids	354	(4)
The Span Function	358	(2)
The Dual of a Matroid	360	(3)
Matroid Minors and Planar Graphs	363	(3)
Matroid Intersection	366	(3)
Matroid Union	369	(3)
Exercises	372	(6)
Ramsey Theory	378	(18)
The Pigeonhole Principle Revisited	378	(2)
Ramsey's Theorem	380	(3)
Ramsey Numbers	383	(3)
Graph Ramsey Theory	386	(2)
Sperner's Lemma and Bandwidth	388	(4)
Exercises	392	(4)
More Extremal Problems	396	(29)
Encodings of Graphs	397	(7)
Branchings and Gossip	404	(4)
List Coloring and Choosability	408	(5)
Partitions Using Paths and Cycles	413	(3)
Circumference	416	(6)
Exercises	422	(3)
Random Graphs	425	(27)
Existence and Expectation	426	(4)
Properties of Almost All Graphs	430	(2)
Threshold Functions	432	(4)
Evolution and Graph Parameters	436	(3)
Connectivity, Cliques, and Coloring	439	(3)
Martingales	442	(6)
Exercises	448	(4)
Eigenvalues of Graphs	452	(19)
The Characteristic Polynomial	453	(3)
Linear Algebra of Real Symmetric Matrices	456	(2)
Eigenvalues and Graph Parameters	458	(2)
Eigenvalues of Regular Graphs	460	(3)
Eigenvalues and Expanders	463	(1)
Strongly Regular Graphs	464	(3)
Exercises	467	(4)
Appendix A Mathematical Background	471	(22)
Sets	471	(4)
Quantifiers and Proofs	475	(4)
Induction and Recurrence	479	(4)
Functions	483	(2)
Counting and Binomial Coefficients	485	(4)
Relations	489	(2)
The Pigeonhole Principle	491	(2)
Appendix B Optimization and Complexity	493	(14)
Intractability	493	(3)
Heuristics and Bounds	496	(3)
NP-Completeness Proofs	499	(6)
Exercises	505	(2)
Appendix C Hints for Selected Exercises	507	(8)
General Discussion	507	(1)
Supplemental Specific Hints	508	(7)
Appendix D Glossary of Terms	515	(18)
Appendix E Supplemental Reading	533	(34)
Appendix F References	567	(2)
Author Index	569	(6)
Subject Index	575

Excerpts

PrefaceGraph theory is a delightful playground for the exploration of proof techniques in discrete mathematics, and its results have applications in many areas of the computing, social, and natural sciences. The design of this book permits usage in a one-semester introduction at the undergraduate or beginning graduate level, or in a patient two-semester introduction. No previous knowledge of graph theory is assumed. Many algorithms and applications are included, but the focus is on understanding the structure of graphs and the techniques used to analyze problems in graph theory.Many textbooks have been written about graph theory. Due to its emphasis on both proofs and applications, the initial model for this book was the elegant text by J.A. Bondy and US.R. Murty,Graph Theory with Applications(Macmillan/NorthHolland 1976). Graph theory is still young, and no consensus has emerged on how the introductory material should be presented. Selection and order of topics, choice of proofs, objectives, and underlying themes are matters of lively debate. Revising this book dozens of times has taught me the difficulty of these decisions. This book is my contribution to the debate. The Second EditionThe revision for the second edition emphasizes making the text easier for the students to learn from and easier for the instructor to teach from. There have not been great changes in the overall content of the book, but the presentation has been modified to make the material more accessible, especially in the early parts of the book. Some of the changes are discussed in more detail later in this preface; here I provide a brief summary. Optional material within non-optional sections is now designated by (*); such material is not used later and can be skipped. Most of it isintendedto be skipped in a one-semester course. When a subsection is marked "optional", the entire subsection is optional, and hence no individual items are starred. For less-experienced students, Appendix A has been added as a reference summary of helpful material on sets, logical statements, induction, counting arguments, binomial coefficients, relations, and the pigeonhole principle. Many proofs have been reworded in more patient language with additional details, and more examples have been added. More than 350 exercises have been added, mostly easier exercises in Chapters 1-7. There are now more than 1200 exercises. More than 100 illustrations have been added; there are now more than 400. In illustrations showing several types of edges, the switch to bold and solid edges instead of solid and dashed edges has increased clarity. Easier.problems are now grouped at the beginning of each exercise section, usable as warm-ups. Statements of some exercises have been clarified. In addition to hints accompanying the exercise statements, there is now an appendix of supplemental hints. For easier access, terms being defined are in bold type, and the vast majority of them appear in Definition items. For easier access, the glossary of notation has been placed on the inside covers. Material involving Eulerian circuits, digraphs, and Turyn's Theorem has been relocated to facilitate more efficient learning. Chapters 6 and 7 have been switched to introduce the idea of planarity earlier, and the section on complexity has become an appendix. The glossary has been improved to eliminate errors and to emphasize items more directly related to the text. FeaturesVarious features of this book facilitate students' efforts to understand the material. There is discussion of proof techniques, more than 1200 exercises of varying difficulty, more than 400 illustrations, and many examples. Proofs are presented in full in the text.Many undergraduates begin a course in graph theory with little exposure to proof techniques.