Graph Theory: A Problem Oriented Approach by Daniel A. Marcus
This is a quick introduction to graph theory loaded with problems. You can quickly read the text content in under an hour. However, the main goal is to work through the problems to understand and prove many of the basic concepts of graph theory. There are bits of "practical" application combined in the introduction to graph theory.
In Pursuit of the Traveling Salesman attempts to be accessible, with a great deal of the text focussed on the history and the people involved. However, it also delves deep into the math. I found myself lost with some of the numbers and optimal solutions. Why are these numbers getting bigger? How are we sure this is the optimal solution. These may have been explained earlier, but I had lost it.
Luckily, the focus is primarily on the people. Even if you get lost with the math, you can follow along with the people. Of key importance is the concept of Linear Programming introduced by George Dantzig. (He had a somewhat auspicious start, solving some "unsolved" statistics problems that he thought were homework.) I got a general idea about how linear programming worked from the text, but it does not really attempt to be a tutorial.
The end of the book presents a number of interesting uses and attempts to solve the traveling salesman problem. Some researchers have used animals grabbing food. Others have attempted to use DNA. People can do a pretty good job with a small set. However, with big sets, they bog down. Some really complex problems involve attempting to trace paths on famous paintings.
The big mystery is still P=NP. Is the salesman problem a difficult problem without an easy solution? Or is there a way that anything can be solved in a reasonable time? There is still a million dollar reward out there, so we may find out.
The book targets a more general audience than just mathematicians. However, it does not skimp on rigor. The opening chapter starts with an introduction to "pure mathematics". The author desires that we can find the joy in math that mathematicians find, and not get bogged down with mechanics. There are plenty of detailed proofs and exercises in the book. At times the book gets pretty deep into the nitty-gritty. However, it will often then bounce back out to more easily acceptable prose. I found it to be a good introduction to graph theory. It contained enough detail to fill in basic understanding gaps and seems to have a good chunk of problems to go through on a re-read.
The Fascinating World of Graph Theory is an introduction to graph theory that focuses on the interesting puzzles and participants in historical context. It introduces core concepts in graph theory as they are needed to tell the story. In doing so, it also provides the biographical history of the mathematicians that were involved in identifying and solving the problems. It is not quite an "introduction" to graph theory, though it does cover basic concepts. A deep math background is not required to start the book. However, the mathematical details and proof due appear. They can be understood in the context of the book (though I did have to occasionally go back to recall what a certain symbol meant.) I did enjoy reading the brief histories of the problems. These were interspersed with the math. There are plenty of problems that could help this be a "math textbook", while there is also historical information for a "general history of science". However, it doesn't quite fit into either category and instead rests somewhere in between.
