
Book DetailsAMS/MAA TextbooksVolume: 11; 2011; 205 pp
Reprinted edition available: TEXT/53
Graph Theory presents a natural, readerfriendly 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 problemoriented 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 KonigEgervary Theorem, Dilworth's Theorem and the Hungarian algorithm to the optional assignment problem, matrices, and latin squares are also explored.

Table of Contents

Cover

Title page

Preface

Contents

Introduction

Path Problems

Coloring Problems

Isomorphic Graphs

Planar Graphs

Disjoint Paths

Shortest Paths

... and More

A Basic Concepts

Equivalent Graphs

Multigraphs

Directed Graphs and Mixed Graphs

Complete Graphs

Cycle Graphs

Paths in a Graph

Open and Closed Paths; Cycles

Subgraphs

The Complement of a Graph

Degrees of Vertices

The Degree Sequence of a Graph

Regular Graphs

Connected and Disconnected Graphs

Components of a Graph

More Problems

Matrices Associated with a Graph

The Degree Sequence Algorithm

B Isomorphic Graphs

More Problems

C Bipartite Graphs

Complete Bipartite Graphs

Bipartite Graphs and Matrices

Cycles in a Bipartite Graph

Cycle Theorem for Bipartite Graphs

Proof of the Cycle Theorem

More Problems

D Trees and Forests

Pruning a Tree

Directed Trees

Spanning Trees

Counting Spanning Trees

Codewords for Trees: Prufer’s Method

More Problems

Three conditions

Cycles and spanning trees

E Spanning Tree Algorithms

Constructing Spanning Trees

Weighted Graphs

Minimal Spanning Trees

Prim’s Algorithm

Tables for Prim’s Algorithm

The Reduction Algorithm

Spanning Trees and Shortest Paths

Minimal Paths in a Weighted Graph

Minimal Path Algorithm, first attempt

Minimal Path Algorithm, revised

Tables for Dijkstra’s Algorithm

Minimal Paths in a Directed Graph

Negative Weights

More Problems

Justification of the reduction algorithm

Justification of Prim’s Algorithm

Justification of Dijkstra’s Algorithm

Justification of Ford’s Algorithm

F Euler Paths

The Königsberg Bridge Problem

Euler Paths in Directed Graphs and Directed Multigraphs

Application of Euler Paths: State diagrams, DeBruijn sequences, and rotating wheels

More Problems

G Hamilton Paths and Cycles

Some Negative Tests

Negative test for bipartite graphs

Subgraph Test for Hamilton paths and cycles

Positive Tests for Hamilton Cycles

The Path/Cycle Principle

Some Proofs

Proof of the Path/Cycle Principle

Proof of the Bondy–Chvatal Theorem

Proof of Dirac’s Theorem

More Problems

Proof of Posa’s Theorem

H Planar Graphs

Regions Formed by a Plane Diagram

Proof that K_5 is NonPlanar, Using Euler’s Formula

NonPlanar Graphs and Kuratowski’s Theorem

More Problems

I Independence and Covering

The Independence Numbers of a Graph

A Graph Game

Covering Sets and Covering Numbers

More Problems

J Connections and Obstructions

Internally Disjoint Paths

EdgeDisjoint Paths

Path Connection Numbers

Blocking Sets

kConnected Graphs

Vertex Cut Sets and Vertex Cut Numbers

The vertex cut number of a graph

More Problems

K Vertex Coloring

The Vertex Coloring Number of a Graph

Vertex Coloring Theorems

Algorithm form of Vertex Coloring Theorem #3:The Upper Bound Algorithm for chi

Why the algorithm works

The Four Color Theorem

Proof of the Six Color Theorem

Proof of the Five Color Theorem

Color switch

Map Coloring

More Problems

Proof of the Four Color Theorem?

Proof of Brooks’ Theorem for regular graphs

L Edge Coloring

The Edge Coloring Number of a Graph

Edge Coloring of Complete Graphs

Edge Coloring of Bipartite Graphs

Edge Color Switch

Proof of Edge Coloring Theorem #3

Application of Edge Coloring: the Scheduling Problem

More Problems

Proof of Edge Coloring Theorem #2

M Matching Theory for Bipartite Graphs

The Max/Min Principle

Proof of the König–Egervary Theorem

The Colored Digraph Construction

Matching Extension Algorithm

Proof of the Colored Digraph Theorem

Matrix Interpretation of the König–Egervary Theorem

Hall’s Theorem and Its Consequences

More Problems

N Applications of Matching Theory

Sets and Representatives

Latin Squares

Permutation Matrices

The Optimal Assignment Problem

More Problems

O CycleFree Digraphs

Chains and Antichains

Chain Decompositions

Proof of Dilworth’s Theorem

More Problems

P Network Flow Theory

Flows in a Network

Path flows

The value of a flow

The matrix of a flow

Capacities in a network

Maximal flow algorithm (first attempt)

The maximal flow algorithm

Cuts and Capacities

The minimal cut algorithm

More Problems

Q Flow Problems with Lower Bounds

The Supply and Demand Problem

Supply and Demand Theorem #1

Supply and Demand Theorem #2 (Gale’s Feasibility Theorem)

The lower capacity problem

Maximizing the flow

Maximal flow algorithm in networks with lower capacities

More Problems

Answers to Selected Problems

Chapter A

Chapter B

Chapter C

Chapter D

Chapter E

Chapter F

Chapter G

Chapter H

Chapter I

Chapter J

Chapter K

Chapter L

Chapter M

Chapter N

Chapter O

Index

About the Author


Reviews

This work could be the basis for a very nice onesemester "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


RequestsReview Copy – for publishers of book reviewsDesk Copy – for instructors who have adopted an AMS textbook for a courseExamination Copy – for faculty considering an AMS textbook for a courseAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Reviews
 Requests
Reprinted edition available: TEXT/53
Graph Theory presents a natural, readerfriendly 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 problemoriented 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 KonigEgervary Theorem, Dilworth's Theorem and the Hungarian algorithm to the optional assignment problem, matrices, and latin squares are also explored.

Cover

Title page

Preface

Contents

Introduction

Path Problems

Coloring Problems

Isomorphic Graphs

Planar Graphs

Disjoint Paths

Shortest Paths

... and More

A Basic Concepts

Equivalent Graphs

Multigraphs

Directed Graphs and Mixed Graphs

Complete Graphs

Cycle Graphs

Paths in a Graph

Open and Closed Paths; Cycles

Subgraphs

The Complement of a Graph

Degrees of Vertices

The Degree Sequence of a Graph

Regular Graphs

Connected and Disconnected Graphs

Components of a Graph

More Problems

Matrices Associated with a Graph

The Degree Sequence Algorithm

B Isomorphic Graphs

More Problems

C Bipartite Graphs

Complete Bipartite Graphs

Bipartite Graphs and Matrices

Cycles in a Bipartite Graph

Cycle Theorem for Bipartite Graphs

Proof of the Cycle Theorem

More Problems

D Trees and Forests

Pruning a Tree

Directed Trees

Spanning Trees

Counting Spanning Trees

Codewords for Trees: Prufer’s Method

More Problems

Three conditions

Cycles and spanning trees

E Spanning Tree Algorithms

Constructing Spanning Trees

Weighted Graphs

Minimal Spanning Trees

Prim’s Algorithm

Tables for Prim’s Algorithm

The Reduction Algorithm

Spanning Trees and Shortest Paths

Minimal Paths in a Weighted Graph

Minimal Path Algorithm, first attempt

Minimal Path Algorithm, revised

Tables for Dijkstra’s Algorithm

Minimal Paths in a Directed Graph

Negative Weights

More Problems

Justification of the reduction algorithm

Justification of Prim’s Algorithm

Justification of Dijkstra’s Algorithm

Justification of Ford’s Algorithm

F Euler Paths

The Königsberg Bridge Problem

Euler Paths in Directed Graphs and Directed Multigraphs

Application of Euler Paths: State diagrams, DeBruijn sequences, and rotating wheels

More Problems

G Hamilton Paths and Cycles

Some Negative Tests

Negative test for bipartite graphs

Subgraph Test for Hamilton paths and cycles

Positive Tests for Hamilton Cycles

The Path/Cycle Principle

Some Proofs

Proof of the Path/Cycle Principle

Proof of the Bondy–Chvatal Theorem

Proof of Dirac’s Theorem

More Problems

Proof of Posa’s Theorem

H Planar Graphs

Regions Formed by a Plane Diagram

Proof that K_5 is NonPlanar, Using Euler’s Formula

NonPlanar Graphs and Kuratowski’s Theorem

More Problems

I Independence and Covering

The Independence Numbers of a Graph

A Graph Game

Covering Sets and Covering Numbers

More Problems

J Connections and Obstructions

Internally Disjoint Paths

EdgeDisjoint Paths

Path Connection Numbers

Blocking Sets

kConnected Graphs

Vertex Cut Sets and Vertex Cut Numbers

The vertex cut number of a graph

More Problems

K Vertex Coloring

The Vertex Coloring Number of a Graph

Vertex Coloring Theorems

Algorithm form of Vertex Coloring Theorem #3:The Upper Bound Algorithm for chi

Why the algorithm works

The Four Color Theorem

Proof of the Six Color Theorem

Proof of the Five Color Theorem

Color switch

Map Coloring

More Problems

Proof of the Four Color Theorem?

Proof of Brooks’ Theorem for regular graphs

L Edge Coloring

The Edge Coloring Number of a Graph

Edge Coloring of Complete Graphs

Edge Coloring of Bipartite Graphs

Edge Color Switch

Proof of Edge Coloring Theorem #3

Application of Edge Coloring: the Scheduling Problem

More Problems

Proof of Edge Coloring Theorem #2

M Matching Theory for Bipartite Graphs

The Max/Min Principle

Proof of the König–Egervary Theorem

The Colored Digraph Construction

Matching Extension Algorithm

Proof of the Colored Digraph Theorem

Matrix Interpretation of the König–Egervary Theorem

Hall’s Theorem and Its Consequences

More Problems

N Applications of Matching Theory

Sets and Representatives

Latin Squares

Permutation Matrices

The Optimal Assignment Problem

More Problems

O CycleFree Digraphs

Chains and Antichains

Chain Decompositions

Proof of Dilworth’s Theorem

More Problems

P Network Flow Theory

Flows in a Network

Path flows

The value of a flow

The matrix of a flow

Capacities in a network

Maximal flow algorithm (first attempt)

The maximal flow algorithm

Cuts and Capacities

The minimal cut algorithm

More Problems

Q Flow Problems with Lower Bounds

The Supply and Demand Problem

Supply and Demand Theorem #1

Supply and Demand Theorem #2 (Gale’s Feasibility Theorem)

The lower capacity problem

Maximizing the flow

Maximal flow algorithm in networks with lower capacities

More Problems

Answers to Selected Problems

Chapter A

Chapter B

Chapter C

Chapter D

Chapter E

Chapter F

Chapter G

Chapter H

Chapter I

Chapter J

Chapter K

Chapter L

Chapter M

Chapter N

Chapter O

Index

About the Author

This work could be the basis for a very nice onesemester "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