Introduction to Graph Theory

by Richard J. Trudeau

A stimulating excursion into pure mathematics aimed at "the mathematically traumatized," but great fun for mathematical hobbyists and serious mathematicians as well. This book leads the reader from simple graphs through planar graphs, Euler's formula, Platonic graphs, coloring, the genus of a graph, Euler walks, Hamilton walks, more. Includes exercises. 1976 edition.

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

224 pages, Paperback

First published February 9, 1994

Reviews

[Ben Gutierrez · Rating 5 out of 5]

What a delight. I picked this up with the intention of deepening my understanding of graphs and graph algorithms. I did learn about graphs, but I don't think I'll ever apply any of it at work or anywhere else.

And I'm fine with that. I'd had this belief that pure mathematics would be somewhere beyond my abilities, but anyone that can do algebra can enjoy this book. It's math for the sake of math. The problems can be explained to a child, but the solutions require rigor and concentration. It's a wonderful space to occupy. The author even offers some areas where an amateur mathematician could try to break some ground.

It's encouraged me to pick up other math books and explore math in ways I would never have considered.

[Alex Iadicicco · Rating 4 out of 5]

Don't let the title fool you, this is far from a math textbook. However, it is definitely not a leisurely read either. The topics can be a bit challenging, especially toward the end, but if you're willing to interact with the author and try your hand at some of the problems, you shouldn't have much trouble following along. Nothing is introduced without first being explained.

This book challenges the widely held notion that mathematics is all about crunching numbers, or is so abstract and subtle that it takes years of study to have meaningful conversations about it. On the contrary, the basics of graph theory require almost no mathematical background, and the only numbers in sight are used for counting things. After defining graphs, Trudeau goes on to discuss topics like planar graphs, graph coloring, Euler walks, etc., using the basic framework of definitions and proofs that characterizes pure mathematics.

I highly recommend this book to anybody who has wondered what higher math is really like. There's no numbers or challengingly abstract concepts here, just simple definitions and logical proofs.

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

Excellent intro to graph theory

And with some comments on math in general. I do wish though that they didn’t all rehash set theory in the beginning. Covers the basics well but gets a bit jumbled towards the end. The coverage gets sparser as it is extended to slightly more complicated matters. Written just as the 4 color theorem was proven. So it is refereed to in the main text as the 4 color conjecture. 1976!
Charmingly old fashioned. Not a single use of the word algorithm. And whilst there is some discussion of methods - for finding paths and circuit - there is no discussion on how long it takes. Aka time complexity. Simpler times. So less rushed.
Good book. Worth a quick read.

[Daniele · Rating 3 out of 5]

I am not a fan of proofs "left to the reader" and unsolved exercises, so I didn't enjoy this book fully. The book spends a lot of words on concepts like sets and induction that might have been avoided (imo). The portion actually about graphs is interesting (there are some long proofs that might be a bit too much and were not fully explained most of the times) but way less enjoyable than I expected. The amount of actual mathematics and rigour makes this book more similar to a study book but the partial proofs and the fact that it's rather old might not make it the best choice for the student. In the end this book isn't best for the mathematics enthusiast nor the the occasional reader.

[Seth Loudermilk · Rating 5 out of 5]

This is an excellent and humorous introduction to graph theory. It may be a little outdated (a certain conjecture specifically) but is still an excellent conversational resource.

[Dean · Rating 3 out of 5]

Applied math >>> pure math. Fight me.

[Kolagani · Rating 4 out of 5]

It was a delightful light read, would recommend it to someone who is not familiar with formal mathematics and interested to know about it. This might be a good starting point.

[Raphael]

https://www.reddit.com/r/books/commen...

[Mickey Smith]

"And these...algebras....are they in the room with us now?"

"Well, only in some paradigms of construction that go out of their way to adhere to defining operations."

*the therapist has begun throttling me with a phone cord*

[Ira Ko · Rating 4 out of 5]

Fascinating read. Trudeau balances depth with brevity, mathematical proofs with humorous commentary.

Trudeau avoids confusing technical jargon, preferring a frank, "down to earth" teaching approach.

Having never been previously exposed to graph theory, I was surprised as to how easily I was able to digest this books contents.

Definitely worth a read for those interested in graphs, math, or theoretical ideas. Bring a pencil!

[An · Rating 2 out of 5]

Very friendly but somewhat outdated book, which is understandable for having been first published in 1976. It still lists the Four Color Theorem as being unproven. Overall it was a great book back in 1976, but there's probably many better contenders now. I would not recommend it if your purpose is to learn Graph Theory in the context of programming, but if you want a gentle introduction to Graph Theory for general purposes, it could work well.

[William Schram · Rating 4 out of 5]

This slim volume does what it says on the cover, making the introduction to graph theory as painless as possible. Contains problems with solutions to certain questions.

[Ida Momennejad · Rating 4 out of 5]

A fast read, very introductory. Useful to have around. I'd recommend a more advanced book if you use graph theory for your research.

[Maaz Muhammad · Rating 4 out of 5]

Between the enthusiasm seeping through the page and the waxing poetic about the wonders of pure math, this book is quite an enjoyable little companion. It assumes no more than a high school level of math, and develops from the ground up what is, in my opinion, one of the most exciting and yet layman-understandable fields of mathematics. A delight to read, I would recommend this book to anyone interested about our world (graph theory underlies applications as diverse as allocating kidneys for saving lives to finding the fastest route to work on Google Maps).


(I should note that for the serious student of mathematics, this book covers barely the first third of an undergraduate intro graph theory course, so look into Douglas West’s graph theory book if you are seeking a more rigorous and complete textbook.)

[Volkan Unsal · Rating 4 out of 5]

This book, like most Dover books, is a hidden gem, a forgotten classic. Despite being 40 years old, written just before the 4-color theorem was proven with the aid of computers -- first theorem to be so proven-- it's a solid introduction to the fundamentals of graph theory. In addition, there is some eye opening background material on the roots of geometry, pure mathematics, mathematical proofs, and topology. If you're curious like I am, you will find a lot to mull over in here. A lot. In fact, it can be too dense to read it all at once. I skimmed over most of the proofs and skipped the exercises entirely, focusing instead on the vocabulary and definitions, but I intend to go back for them someday.

[Mostafa Alkady · Rating 5 out of 5]

This is easily one of the best maths textbooks I've read in a while. The approach to Graph Theory here is from the pure mathematics side and has the theory-lemma-proof style. However, it's a very easy read (yes, you can really read it on a bus). If you have no idea what graph theory is about and you want an easy start that assumes no prior knowledge of anything, this book is for you.

A little caveat: This book was written before the four-color theorem was proved (ironically, in the same year: 1976), so it's a little outdated in this regard. He also mentioned that a bunch of other minor results hadn't been proven by the time he wrote the book, so take these with a grain of salt.

[Cjn · Rating 5 out of 5]

As someone who doesn't have such a strong math background, I found his 'introduction to proofs' section really useful, even beyond the scope of graph theory. The content is a little bit elementary, but generally well suited for someone new to this field. I guess I was looking for more real world examples, as I am a natural scientist reading this with applications in mind. But the intent of this book is to lay out the theoretical foundations, which is appreciated. His writing also made reading it enjoyable (in addition to clear), which can't be said for most math textbooks.

[Nico Grassetto · Rating 4 out of 5]

It lives up to its promise.
This is a nice introduction to graph theory . Don't get me wrong, this is a math heavy book but I found some of the topics explained in a better way than by my undergrad teacher.
I used it as complementary resource.
Though, for people seeking an algorithm-oriented book, this one focuses more on the underlying principles and proofs rather than graph theory algorithms.
Moreover, it is not presented from an applied perspective, and therefore the reader must expect the formalities that mathematics brings along.
All in all, it was a good read!

[Eric · Rating 5 out of 5]

This was a great introduction, as the title promised. It had just the right mix of theory, proof, and hand-holding I was looking for. It really piqued my interest in graph theory, which is now nearly on par with my fascination with group theory (and that’s really saying something). The fact that it took my so long to read has nothing to do with the book itself, and everything to do with my free time.

[Dakota Palmer · Rating 4 out of 5]

Really Well made graph theory text, I did find it to be dated in some aspects. Most notably its reference to the four-color theorem as being unsolved, however, thankfully that was fixed in an afterwords. A few sections were far more difficult than the rest of the text, especially the platonic graphs of genus > 0 section. Overall I really liked the text, but I had to look for supplementary materials for some of the harder portions.

[Ryan · Rating 5 out of 5]

Trudeau really wants the reader to understand and enjoy graph theory. His thought process is accessible, and he's interested in finding an intuitive way to get to a result. Sometimes that intuition is wrong, and the author is right there with you expressing his surprise, which reminds you that mistakes are inherent to furthering understanding.

[Gabriel Djebbar · Rating 5 out of 5]

I really liked the way the author introduced the subject, it was really encouraging for me. I particularly liked how he introduced it as a Game (even expanding this concept of game to other mathematical theories) which is played through the rules of logic. I didn't do all the exercise, but I still feel I learned quite a lot. I'll probably reread it this year.

[Andrew Breza · Rating 5 out of 5]

A terrific textbook about the pure math aspects of graph theory. The light tone belies serious mathematical rigor. While many math writers throw proofs at the reader as an afterthought, Trudeau delights in proving the book's theorems.

[Dimitri Bianco · Rating 4 out of 5]

A great book for non-math people with some insight to what a proof is and why they are hard to come up with. The beginning of the book is more like brain teasers which is a fun approach as it is pure math.

[Elsa Frankel · Rating 5 out of 5]

My friend gave me this book when I was 16, three months after sneaking me into his discrete math class... the opening section fascinated me when I barely knew any graph theory, and continues to be a great reference, three years later, for research.

[Paolo Simeone · Rating 3 out of 5]

An interesting ride.

[Murat Şeker · Rating 5 out of 5]

Brilliant read. Proofs towards the end are a bit cumbersome to follow for lazy but totally manageable.

[Daniel Hoffman · Rating 5 out of 5]

Solid introduction to the field. I finished this in a few days and enjoyed it

[Ben · Rating 4 out of 5]

Clear and readable - I wish I'd encountered more math like this earlier.

[Nathan · Rating 3 out of 5]

The tone is sincere if a bit condescending at times.