## A Beginner's Guide to Graph TheoryBecause 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 |

225 | |

### Other editions - View all

### Common terms and phrases

algorithm augmenting path bipartite graph blue bridge chromatic number chromatic polynomial complete graph component of G connected graph Consider construct Corollary critical paths cubic graph cutpoint cutset subspace cycle subspace defined deleting digraph directed path disjoint edge joining edge xy edge-coloring edges incident edges of G endpoints Euler walk example factor Find finite G contains graph contains graph G Graph Theory Graphs for Exercise graphs in Figure Hamilton cycle integers isomorphic label least Lemma matrix maximal flow maximum monochromatic triangle multigraph nearest vertex number of edges number of vertices odd components one-factor partition Petersen graph planar graph precede Proof Prove Ramsey's Theorem regular graph Select a vertex separating cut sequence set of vertices shortest path shown in Figure subset sum-free Suppose G tasks Theorem tournament Traveling Salesman problem vector space vertex of degree vertex-set vertices adjacent vertices of G weight write

### 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.