Introduction to Graph Theory

by Gary Chartrand

Graph theory is used today in the physical sciences, social sciences, computer science and other areas. Introductory Graph Theory presents a nontechnical introduction to this exciting field in a clear, lively and informative style.

Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics.

Genres: Mathematics, Technical, Reference, Computer Science, Textbooks, Nonfiction, Science

Paperback

First published December 1, 1984

About the author

Gary Theodore Chartrand is a professor emeritus of mathematics at Western Michigan University

Reviews

[J. · Rating 3 out of 5]

The title here is a bit misleading. A mathematician won't find much in here that's helpful, but it would make a really good textbook for a nontechnical math class--the sort of 'shotgun' math class lots of liberal arts students take instead of calculus. The general setup for a chapter is: Introduce a classic problem, define some basic graph theory terms that would be helpful, prove a couple theorems, give a couple of examples. So nothing ever gets very deep, but it does present at least the basic ideas of a lot of things. So: it is what it is--easy to read, with some good motivation and problems, but not very technical.

[A. Jesse · Rating 5 out of 5]

If you are a software developer, then from time to time you will have to solve an Interesting Problem in optimization, such as finding the best matches on a dating site, or the right sharding key for a database cluster. As often as not, such problems can be expressed as a network of interrelated nodes, and if so, the problem probably has a name and a known solution in graph theory. Your problem now is to know that name so you can Google for the solution.

This book is a charming, breezy intro to graph theory, covering basic terminology and some theorems related to planar graphs, topology, map-coloring, matching, and optimization. I more-or-less minored in math in college and have taken a handful of courses over subsequent 10 years, and I found nearly every proof and problem accessible, sometimes requiring some effort, but never insurmountably hard. The book promises to be introductory, and I have now been introduced -- the next time I run into a stumper while I'm building software, I feel I have a far better chance of recognizing it as a known problem with a standard solution.

[Greg · Rating 3 out of 5]

This book is a good introduction to using graphs to solve common problems in many different fields and solving various puzzles. It is for a non-mathematician audience because it keeps notations to a minimum and there is no heavy duty matrix algebra. I can only recommend the book as recreational reading for the curious or to learn some basics. It could not be used in a course other than with high school students or undergraduates.

[Anthony O'Connor · Rating 5 out of 5]

A superb introduction to basic graph theory.
Covers all the main topics thoroughly and clearly.
There are a few simple proofs of important elementary theorems that are a pleasure to go through.
This is not a common experience. Most math books even at an introductory level are not well written and are not easy to read.
It gives great examples of common structures and experiences from which these abstractions
naturally arise - and the evident importance of being able to solve the major problems - such
as finding paths and circuits. Coloring problems, matching problems. Et al.
Graphs and solving problems about graphs are basic to and underlie most problem solving about most things. Fundamental to Math and computing.
This book gets you off to a good start.

[Neil Foxman · Rating 3 out of 5]

The book introduces and describes some common graph theory problems in a fun and approachable way. It also provides a good discussion and visualizations for the problems to focus on how to think about the problems.
I would caution that the book steers clear from getting into the technical parts of the proofs and mathematics, and focuses more on understanding the problem than say creating algorithms.

[Harris Ferguson · Rating 5 out of 5]

Thoughtful examples and clear proofs. Understandable even without lots of Uni level math, with lots of applications. Anyone taking an undergrad graph theory course will enjoy.

[Ameer · Rating 5 out of 5]

Amazing tour over the basics of graph theory. My rating of the book may be biased by the fact that graph theory is an amazing subject than the style or contents of the book itself. As far as I know the content was elementary but covered a wide range of interesting topics (Hamiltonian Graphs, Balanced Graphs, Planar Graphs, Orientable Graphs, Chromatic Numbers, to name the immediately memorable). The proofs when given were easy enough to follow if you thought about them (at most a page or two), and the difficult proofs were omitted which I liked so as not to spend too much time caught up in them so I could focus on the content. They were included in the appendices if you do want to take a look though. The only part I didn't like was the diversion into social theory (the bit about parent child adult) which seemed a bit dated and didn't really contain any useful info and was more of an illustration that graphs can be used to model things outside graphs themselves more than anything else, a very minor complaint though.

[Darin · Rating 3 out of 5]

The first chapter is on mathematical modeling in general while the second chapter covers graph theory terminology. I have studied graph theory before and still found some of the definitions to be confusing.

The remaining chapters are on various problems and how to model them using graphs (the original title of this book was Graphs as Mathematical Models). This is where the book really shines.
The author even represents the Towers of Hanoi problem as a graph. While I don't think the book is good for learning the names for various kinds of graphs, it provides much motivation for why learning about graphs can be useful.

[Kellan]

on reco from Bill deHora

[David · Rating 5 out of 5]

Chartrand makes graph theory fun.

[Namratha Santhosh]

Gary