# A Beginner's Guide to Graph Theory

Springer Science & Business Media, Jun 15, 2000 - Mathematics - 230 pages
Because of its wide applicability, graph theory is one of the fast-growing areas of modern mathematics. Graphs arise as mathematical models in areas as diverse as management science, chemistry, resource planning, and computing. Moreover, the theory of graphs provides a spectrum of methods of proof and is a good train ing ground for pure mathematics. Thus, many colleges and universities provide a first course in graph theory that is intended primarily for mathematics majors but accessible to other students at the senior Ievel. This text is intended for such a course. I have presented this course many times. Over the years classes have included mainly mathematics and computer science majors, but there have been several engineers and occasional psychologists as weil. Often undergraduate and graduate students are in the same dass. Many instructors will no doubt find themselves with similar mixed groups. lt is to be expected that anyone enrolling in a senior Ievel mathematics course will be comfortable with mathematical ideas and notation. In particular, I assume the reader is familiar with the basic concepts of set theory, has seen mathematical induction, and has a passing acquaintance with matrices and algebra. However, one cannot assume that the students in a first graph theory course will have a good knowledge of any specific advanced area. My reaction to this is to avoid too many specific prerequisites. The main requirement, namely a little mathematical maturity, may have been acquired in a variety of ways.

### What people are saying -Write a review

User Review - Flag as inappropriate

goodprvs

### Contents

 Graphs 1 12 Some Definitions 4 13 Degree 11 Walks Paths and Cycles 15 22 Weights and Shortest Paths 19 23 Euler Walks 23 24 Hamilton Cycles 26 25 The Traveling Salesman Problem 31
 Planarity 105 82 Eulers Formula 108 83 Maps Graphs and Planarity 111 Ramsey Theory 115 92 Ramsey Multiplicity 120 93 Application of SumFree Sets 123 94 Bounds on Classical Ramsey Numbers 125 95 The General Case of Ramseys Theorem 129

 Cuts and Connectivity 35 32 Blocks 37 33 Connectivity 40 Trees 43 42 Spanning Trees 46 43 Minimal Spanning Trees 51 Linear Spaces Associated with Graphs 55 52 The Power Set as a Vector Space 56 53 The Vector Spaces Associated with a Graph 58 54 The Cutset Subspace 60 55 Bases and Spanning Trees 63 Factorizations 69 62 Tournament Applications of OneFactorizations 75 63 A General Existence Theorem 77 64 Graphs Without OneFactors 81 Graph Colorings 85 72 Brooks Theorem 89 73 Counting Vertex Colorings 91 74 EdgeColorings 96 75 Class 2 Graphs 99
 Digraphs 131 102 Orientations and Tournaments 135 103 Directed Euler Walks 139 Critical Paths 143 112 Critical Path Analysis 146 113 Critical Paths Under Uncertainty 153 Flows in Networks 159 122 Maximal Flows 165 123 The Max Flow Min Cut Theorem 171 124 The Max Flow Min Cut Algorithm 173 125 Supply and Demand Problems 179 Computational Considerations 185 132 Data Structures 188 133 Some Graph Algorithms 190 134 Intractability 194 References 197 Hints 205 Answers and Solutions 207 Index 225 Copyright

### Popular passages

Page 203 - TW HAYNES, ST HEDETNIEMI, AND PJ SLATER. Fundamentals of domination in graphs.
Page 203 - JW Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).
Page 204 - Roberts, FS, Graph Theory and its Applications to Problems of Society, CBMS-NSF Monograph 29, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1978.