## Books Added 1 Aug 2008: Graph Theory

I have had a long-standing question: why is the usual triangulation of a torus so large? It is a square with 18 triangles. Why so many?

While looking through algebraic topology books for more information about simplicial complexes – which is supplementary material for Bloch (“A First Course in Geometric Topology….” – I found the answer. Well, I found a clue. I found an inequality, which implied that the minimum number of triangles was 14 in any possible triangulation of the torus.

What I didn’t find was a proof of that inequality, and I couldn’t work it out for myself.

Eventually, in another algebraic topology book, I found another clue, and it was enough to let me work out the first inequality.

Along the way I found some pretty interesting things, and I want to chatter about them. The result will not really be math, but more in the nature of a travel guide.

Well, no, not even that detailed. More in the nature of some really cool pictures from a foreign country.

The search took me into both algebraic topology and graph theory. Before I put out the posts (there will be at least two), I need to put out some bibliography.

The graph theory is easy. I only own 4 books on graph theory, and I acquired one of them just this week.

So, the following books on graph theory have been added to the bibliography.

There are two old classics. Biggs et al. is a collection of 37 original papers that helped found graph theory. Where necessary, they have been translated into English, and the authors have written whatever introductory material was necessary before each paper.

Here you will find Euler’s foundational paper on the Konigsberg bridges, of course; but also Kirchhoff’s paper using graph theory for electric circuits. (Yes, the use of graphs for simplifying the application of Kirchhoff’s laws goes back to Kirchhoff himself!)

Among other things you will find Euler’s polyhedral formula (V – E + F = 2), chemical graphs, the four-color problem, and planar graphs.

The other old classic is Bondy & Murty “Graph Theory with Applications”. Every chapter ends with “Applications”. I like that. In fact I would be unhappy without them.

I love the terminology of graph theory: an acyclic graph is also called a forest; each component is called a tree (so a tree is a connected acyclic graph). But after a while I begin to feel like I’m just proving random facts about random things. I’d like to do better.

The other two books? One is a brand new book by Bondy & Murty. They say in the introduction that it began as a second edition. It grew too much, and the different title reflects that growth. (It wouldn’t have been the first “second edition” to be a different book.)

Realistically speaking, I could have mentioned the book, said I didn’t own it, and left it up to you to decide whether to buy it. OTOH, if I try to order it myself and find that you all have exhausted Amazon’s supply… well, that would be terrible.

I just had to buy the book. (That happens a lot, for one reason or another.)

It is a much larger book than it’s predecessor. (Have I ever seen a second edition smaller than the first? Only when the book split into multiple volumes.) It still contains applications, but you’ll find them listed under “problems” in the index. OTOH, you’ll also find a detailed sublist of “proof techniques” in the index. I think that’s way cool. (You will find elementary techniques such as induction and contradiction, intermediate techniques such as the pigeonhole principle, as well as techniques specific to graph theory.)

The book can be used as an undergraduate text: just read the first few sections of most of the chapters; or as a graduate text: read it all!

One major caveat: there is a second printing under way. According to the web site (here) it will, of course, correct errata, but it will also be “slightly reorganized”. I’m not sure what that bodes, but you might want to wait for the second printing.

Finally, I have a book by Bollobas. I can tell from the price sticker that I bought it during a Springer “yellow sale” in 2003, for about 1/3 off. I am sure I bought it just because I wanted a more modern book than the old classics.

I have no regrets. Quite the contrary. The first chapter, fundamentals, is a rather compact presentation: graphs, trees, Euler & Hamiltonian cycles, and planar graphs. Whew! But it’s well written, and it’s nice to have what amounts to: if I only get to show you one chapter of graph theory, well here it is.

The second chapter is electrical networks. Good, we have some applications.

But then section 2 of the second chapter uses electrical networks to search for “squared squares” and “squared rectangles”. Hey what? An example of a squared rectangle is the following (where each integer is the length of a side of the square in which it sits, and the whole thing is a 33×32 rectangle):

I know some of those! I played with them several years ago.

I am looking forward to Bollobas.

I’m getting excited about doing graph theory. I’m pretty sure I’ll go through the old Bondy & Murty first, but with the history book handy. (If I didn’t have the old Bondy & Murty, I would work the first few sections of each chapter of the new one. Having the old one, I view the new one as a reference book. Perhaps I’m wrong to do that.)

After I had worked both of those, I would hit Bollobas.

Or maybe I’ll do the first chapter of Bollobas, and then the other two….

I’ll let you know.

Bollobas, Bela. Modern Graph Theory. Springer, corrected printing 2002.
ISBN 0 387 98488 7.
[graph theory;1 Aug 2008]
“Graduate Texts in Mathematics”. I haven’t worked thru it yet, but its first two chapters look spectacular, and it has lots of exercises. The first chapter is an introductory overview, possible because we can get powerful theorems early on. The second chapter is a delightful looking digression on electrical networks and subdivisions of rectangles.

Bondy, J.A. and Murty, U.S.R. Graph Theory with Applications. North Holland, 1976.
ISBN 0 444 19451 7.
[graph theory;1 Aug 2008]
This is the old classic. Every chapter ends with applications. Just looking thu it makes me want to curl up and work thru it.

Bondy, J.A. and Murty, U.S.R. Graph Theory. Springer, 2008.
ISBN 978 1 84628 969 9.
[graph theory;1 Aug 2008]
“Graduate Texts in Mathematics”. Looks as though it could be used as an undergraduate text, or as a second-year graduate text getting one ready for research; just decide how far into each chapter to read.

Biggs, Norman L, Lloyd; E. Keith; Wilson, Robin J. Graph Theory 1736–1936.
ISBN 0 19 853901 0.
[graph theory;1 Aug 2008]
This seems a very gentle introduction, although it does have proofs. It’s a collection of the original papers about graph theory – translated into english, with substantial commentary before each.

### 2 Responses to “Books Added 1 Aug 2008: Graph Theory”

1. Dave Peterson Says:

Dear Rip,

Have you gone through Chapter 1 of the Bollobas book yet? I just did and there is an annoying typo at the bottom of page 6. There he says that the graph in Figure I.1 is bipartite. Unfortunately the graph contains several triangles, so it can’t possibly be bipartite (cf. Theorem 4 on page 9). However, it does appear to be tripartite.

This is probably just a trivial typo but it bothers me when someone of Bollobas’ stature does something like this and it lies uncorrected for a decade.

• rip Says:

Hi Dave,

I’ve looked thru my copy and I have to agree with you. Incidentally, mine is a 2002 corrected printing.