**AMS/MAA Textbooks**

Volume: 11;
2011;
205 pp;
Softcover

Print ISBN: 978-0-88385-772-4

Product Code: TEXT/11

List Price: $59.00

AMS Member Price: $44.25

MAA Member Price: $44.25

**Electronic ISBN: 978-0-88385-969-8
Product Code: TEXT/11.E**

List Price: $59.00

AMS Member Price: $44.25

MAA Member Price: $44.25

# Graph Theory: A Problem Oriented Approach

Share this page
*Daniel A. Marcus*

MAA Press: An Imprint of the American Mathematical Society

Graph Theory presents a natural,
reader-friendly way to learn some of the essential ideas of graph
theory starting from first principles. The format is similar to the
companion text, Combinatorics: A Problem Oriented Approach also by
Daniel A. Marcus, in that it combines the features of a textbook with
those of a problem workbook. The material is presented through a
series of approximately 360 strategically placed problems with
connecting text. This is supplemented by 280 additional problems that
are intended to be used as homework assignments. Concepts of graph
theory are introduced, developed, and reinforced by working through
leading questions posed in the problems.

This problem-oriented
format is intended to promote active involvement by the reader while
always providing clear direction. This approach figures prominently on
the presentation of proofs, which become more frequent and elaborate
as the book progresses. Arguments are arranged in digestible chunks
and always appear along with concrete examples to keep the readers
firmly grounded in their motivation.

Spanning tree algorithms,
Euler paths, Hamilton paths and cycles, planar graphs, independence
and covering, connections and obstructions, and vertex and edge
colorings make up the core of the book. Hall's Theorem, the
Konig-Egervary Theorem, Dilworth's Theorem and the Hungarian algorithm
to the optional assignment problem, matrices, and latin squares are
also explored.

#### Reviews & Endorsements

This work could be the basis for a very nice one-semester "transition" course in which students evolve from users of theorems to creators of proofs. With their intuitive appeal and pictorial representations, graphs may be a better basis than analysis and limits for such a transtion.

-- Choice

# Table of Contents

## Graph Theory: A Problem Oriented Approach

- Cover cover11
- Title page iii4
- Preface ix10
- Contents xiii14
- Introduction 118
- A Basic Concepts 926
- Equivalent Graphs 926
- Multigraphs 1027
- Directed Graphs and Mixed Graphs 1128
- Complete Graphs 1128
- Cycle Graphs 1128
- Paths in a Graph 1128
- Open and Closed Paths; Cycles 1229
- Subgraphs 1330
- The Complement of a Graph 1330
- Degrees of Vertices 1330
- The Degree Sequence of a Graph 1431
- Regular Graphs 1532
- Connected and Disconnected Graphs 1532
- Components of a Graph 1532
- More Problems 1633

- B Isomorphic Graphs 2138
- C Bipartite Graphs 2542
- Complete Bipartite Graphs 2643
- D Trees and Forests 3148
- E Spanning Tree Algorithms 4158
- Constructing Spanning Trees 4158
- Weighted Graphs 4158
- Minimal Spanning Trees 4259
- Prim’s Algorithm 4259
- Tables for Prim’s Algorithm 4360
- The Reduction Algorithm 4360
- Spanning Trees and Shortest Paths 4461
- Minimal Paths in a Weighted Graph 4562
- Minimal Path Algorithm, first attempt 4562
- Minimal Path Algorithm, revised 4663
- Tables for Dijkstra’s Algorithm 4663
- Minimal Paths in a Directed Graph 4865
- Negative Weights 4865
- More Problems 5168

- F Euler Paths 5774
- G Hamilton Paths and Cycles 6582
- H Planar Graphs 7794
- I Independence and Covering 85102
- J Connections and Obstructions 95112
- K Vertex Coloring 103120
- The Vertex Coloring Number of a Graph 103120
- Vertex Coloring Theorems 104121
- Algorithm form of Vertex Coloring Theorem #3:The Upper Bound Algorithm for chi 107124
- Why the algorithm works 108125
- The Four Color Theorem 108125
- Proof of the Six Color Theorem 108125
- Proof of the Five Color Theorem 108125
- Color switch 109126
- Map Coloring 110127
- More Problems 111128

- L Edge Coloring 119136
- M Matching Theory for Bipartite Graphs 131148
- The Max/Min Principle 132149
- Proof of the König–Egervary Theorem 133150
- The Colored Digraph Construction 133150
- Matching Extension Algorithm 135152
- Proof of the Colored Digraph Theorem 135152
- Matrix Interpretation of the König–Egervary Theorem 136153
- Hall’s Theorem and Its Consequences 138155
- More Problems 139156

- N Applications of Matching Theory 143160
- O Cycle-Free Digraphs 153170
- P Network Flow Theory 161178
- Q Flow Problems with Lower Bounds 175192
- Answers to Selected Problems 187204
- Index 201218
- About the Author 205222