Tag Info

20

I suggest you discuss the Seven bridges of Königsberg problem (the problem that essentially started the field of graph theory), then discuss the Three utilities problem. For each, discuss the problem first, then introduce the definitions, then perhaps give a sketch of a proof. The first problem allows you to introduce the concepts of vertex, edge, walk, ...

12

I study pursuit-evasion games on graphs, so I will recommend using the cops & robbers game as a way to introduce graph theoretic terminology, concepts, and examples. It should also keep the tone informal and recreational, which will do far more (I believe) to actually inspire the students to study more mathematics. Below are the rules of the game, so ...

6

I would try to keep it heavy on sugar and light on medicine. In particular emphasize visual representations more than precise terms that students don't know (or even worse, symbol soup). Maybe something like this: https://www.youtube.com/watch?v=iW_LkYiuTKE For what it's worth, I find this very similar to the issue of alkane isomers. Just got done Zoom ...

5

I always introduce graph theory with the Königsberg Bridges, as Joel Reyes Noche suggested in his answer. Years ago, I went to a wonderful math talk that used this problem to describe 5 or more stages of what I'll call mathematizing. There was the physical problem. Then drawing it to be able to "walk" the bridges with a pencil, instead of for real. Then ...

5

I use "Introductory Graph Theory" by Gary Chartrand (Dover, 1985) because it is heavy on applications and introduces some of the concepts only after presenting examples that would need them. (A warning though, some of its definitions are not the same as those used by other authors.) There is a newer book, "The Fascinating World of Graph Theory" by Arthur ...

5

You might include results on coloring plane graphs: The Art Gallery Theorem: $3$-coloring. Using Euler's theorem to prove that there must be a vertex of degree at most $5$. From there to $6$-coloring plane graphs. $5$-coloring is more difficult, but there is a nice exposition in Proofs from THE BOOK. Finally, sketch a history of the $4$-color theorem. &...

4

The Canvas class for Dartmouth's Spring 2020 course in Graph Theory, Math 38, seems to be mostly open. According to the syllabus, the course uses the 2nd edition of West's Introduction to Graph Theory. Course Description This course will cover the fundamental concepts of graph theory: simple graphs, digraphs, Eulerian and Hamiltonian graphs, trees, ...

3

There are no Amazon reviews. Doesn't seem like a popular title. (Just an indicator, not a Euclidean proof...but a negative note.) The preface says that it is approaching teaching all of graph theory via this one graph as motivation. Seems rather non-standard. Again, not Euclidean proof, but a negative indicator. If you are self studying AND a weak ...

3

Here's a drawing of a house Can you draw it without lifting your pencil? What about if the roof is removed? What about two houses side-to-side? Here’s the floor plan for a house with some doors (some of which lead to the outside) Is it possible to draw a path that walks through every door, without going through any door twice? Then you can talk about ...

2

There is quite a bit of literature on this topic in the "Graph Drawing" community. Although the goal is algorithms for automatically drawing graphs, several papers offer criteria which could be followed by hand. I'll mention two. (1) Eades, Peter, and Lin Xuemin. "How to draw a directed graph." In 1989 IEEE Workshop on Visual Languages, ...

2

Typical topics are the Dijkstra and Floyd algorithms to find the shortest way between two nodes in a graph (used e.g. for NPC wayfinding in games, navigation etc.) or typical problems of IT theory (e.g. https://en.wikipedia.org/wiki/Graph_coloring vertex coloring). You could also cover neural net types that are build upon a graph-like structure. Usually, ...

1

That book gets ripped pretty hard on Amazon. The Dover texts by Trudeau and Chartrand are supposedly easier and friendlier, per reviews. And will be cheap, since Dover. If you want to develop familiarity and speed, I would certainly not eschew (i.e. I would do) problems that are repetitive. You'll get more practiced at the concept. Also more practiced at ...

1

For completeness, I do recommend several "Moore method"/inquiry-based sets of notes found at the Journal of Inquiry-Based Learning in Mathematics website. I have successfully used a pastiche of these resources for a first course, needing only basic sets and induction as background. Graph theory is very ideally suited to such presentation. For a fairly ...

Only top voted, non community-wiki answers of a minimum length are eligible