Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Graph Theory: A Problem Oriented Approach
 
Daniel A. Marcus
Graph Theory
MAA Press: An Imprint of the American Mathematical Society
Now available in new edition: TEXT/53
Graph Theory
Click above image for expanded view
Graph Theory: A Problem Oriented Approach
Daniel A. Marcus
MAA Press: An Imprint of the American Mathematical Society
Now available in new edition: TEXT/53
  • Book Details
     
     
    AMS/MAA Textbooks
    Volume: 11; 2011; 205 pp

    Reprinted edition available: TEXT/53

    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.
  • 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 Non-Planar, Using Euler’s Formula
    • Non-Planar 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
    • Edge-Disjoint Paths
    • Path Connection Numbers
    • Blocking Sets
    • k-Connected 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 Cycle-Free 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 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
AMS/MAA Textbooks
Volume: 11; 2011; 205 pp

Reprinted edition available: TEXT/53

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.
  • 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 Non-Planar, Using Euler’s Formula
  • Non-Planar 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
  • Edge-Disjoint Paths
  • Path Connection Numbers
  • Blocking Sets
  • k-Connected 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 Cycle-Free 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 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
Review Copy – for publishers of book reviews
Desk Copy – for instructors who have adopted an AMS textbook for a course
Examination Copy – for faculty considering an AMS textbook for a course
Accessibility – to request an alternate format of an AMS title
Powered by MathJax
Please select which format for which you are requesting permissions.