Content for a 40-minute lecture on graph theory for high schoolers

Question

I'm due to deliver a session on graph theory for 16–17-year old students (UK sixth formers) as a taster of what studying mathematics at university is like. What would you recommend as content, and a 'route' through the content for such a talk? There will be a short set of exercises to accompany the talk.

My aim is to mimic some of the features of an undergraduate lecture, especially in terms of starting with formal definitions and writing proofs of formal statements. I'm not specifically looking for it to be dry but on this occasion I am willing to sacrifice being engaging and dynamic to some extent!

At present I have the definitions of a graph/subgraph, walks/paths/cycles, trees and planar graphs, but it feels a bit flimsy, for want of a better word. The section on planar graphs is only there in order to enable a question about proving the Euler faces/edges/vertices theorem and since I want to leave that for the exercises I don't really have much else to say about planar graphs in general.

You may want to start with sets, because this is what graphs are. Also, presenting graphs as dots and lines is not necessarily the best way to think of them. "Dots and lines" by Richard J Trudeau is reasonably academic yet not too math-y. — Rusty Core, May 08 '20 at 23:00
Perhaps you'll find chapter 4 of Discrete Mathematics, by Oscar Levin, helpful: http://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html — Sue VanHattum, May 09 '20 at 00:33
@SueVanHattum I came across that while pursuing some of the ideas from the answers here and have found it extremely useful! — dbmag9, May 09 '20 at 10:13
@RustyCore Don't worry, I have done so; the previous session is on sets and relations so nicely provides the basic framework of sets and ordered pairs. — dbmag9, May 09 '20 at 10:14
DFS and BFS are pretty simple algorithms to explain and they come up in a lot of situations. A comparison of the compexity & memory use between DFS and BFS might also be cool but maybe too advanced. — xdhmoore, May 10 '20 at 04:00

score 20 · Accepted Answer · answered May 08 '20 at 14:09

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, and path; the second allows you to talk about complete bipartite graphs, and planar (and nonplanar) graphs. Both involve proving that something is impossible, something that I think is a very useful skill.

answered May 08 '20 at 14:09

JRN

10,796
2
37
80

1

Seven bridges of Königsberg problem is boring and toy because it's an unweighted graph. More interesting is a weighted graph, e.g. "What's the shortest total flight time from Anchorage, Alaska (ANC) to Guadalara, Mexico (GDL), given a graph where airports are nodes and edge weights are flight times?" (and ignoring layover times) – smci May 08 '20 at 22:18
28

@smci: "Seven bridges of Königsberg problem is boring and toy". Right. Only an idiot like Euler would write a paper about it. – Torsten Schoeneberg May 09 '20 at 01:59
12

The point of the Seven Bridges problem is that it motivates the abstraction from districts and bridges to points and lines sketched on paper, and further to vertices as elements of a set and edges as elements of an other set together with an incidence relation between them – Hagen von Eitzen May 09 '20 at 10:03
8

@smci That problem is totally boring: If all flight times are positive, it is obvious from the finiteness of the graph that either a minimum exists or no connection at all exists - and that's it – Hagen von Eitzen May 09 '20 at 10:08
3

@TorstenSchoeneberg I joined this community specifically to upvote that comment! – Avrohom Yisroel May 10 '20 at 16:48
5

My university math lectures (introductory: 1st and 2nd year of physics) were very dynamic, the prof was constantly teasing us with some problems and was leaving us a few minutes to try ourselves before going further. Showing them a picture of the bridges and asking to try for a few minutes will help them to get into the problem. OTOH our algebra lectures were super formal and I fell asleep twice, something which never happened elsewhere. Please note that not all of them will learn math afterwards. – WoJ May 10 '20 at 20:03
It's probably also really helpful to show at least one solid real-world application, particularly for the type of talk OP seems to be describing. Especially for learning students, it's important to connect the dots, so to speak, between the theoretical prototypes and the dirty real-world problems where this mathematics is used. Often it's more the latter that hooks the kids attention. – J... May 11 '20 at 19:01
@TorstenSchoeneberg: the Seven Bridges of Königsberg problem has plenty of solutions, once we relax the totally arbitrary restriction that you can't revisit a node/edge (justify it please). (That's the sort of obvious thing a kid is more likely to point out than a graduate, i.e. it's anticorrelated with education.) And I said 7BoK 'is' toy now in the 21st century; I never said 7BoK was toy back in 1736, when it represented a hitherto-unstudied field ('geometry of position'). But as of these days, weighted graphs are better representation for many real-world problems of general interest... – smci May 21 '20 at 19:59
...problems of general interest, e.g. "You want to visit your relative in New York in the month of July, what's the shortest total flight time to get there on a roundtrip ticket, given your budget is max $400, and you can take at most one connection?" or "How long does it take to get home to your house from SF downtown, if you can take two modes of transport?" – smci May 21 '20 at 20:01
@AvrohomYisroel: see above, and don't be so fast to upvote distortions. I said 7BoK 'is' toy now in the 21st century; I never said 7BoK was toy back in 1736, when it represented a hitherto-unstudied field ('geometry of position'). The terms 'is', 'was', 'used to be' clearly mean different things. – smci May 21 '20 at 20:05
2

@smci I'm not sure what you mean. I voted for Torsten's comment about Euler writing a paper, I wasn't referring to any of your comments at all. – Avrohom Yisroel May 22 '20 at 10:32
@smci:Yesterday I came across a difficult chess problem, but then I noticed it had plenty of solutions once we ignore the totally arbitrary restriction that there was a white knight on f3. I wrote to the chess magazine, asking them to justify the placing of that knight. – Torsten Schoeneberg Jun 03 '20 at 06:41
1

On a more serious note, good that you qualify your statement that the problem is boring and toy. You admit it was not so for Euler, and his intended audience, in 1736; I admit it is boring for you and me, in 2020; now the question is, is the graph theory background of the group of high schoolers OP prepares a lecture for closer to ours, or to that of the learned men and women of 1736? As @HagenvonEitzen points out, this is a good problem to motivate abstraction to show a surprising impossibility result. This is the beauty of math. Whereas the problems you propose ... – Torsten Schoeneberg Jun 03 '20 at 06:49
... Whereas the problems you propose play into the idea that the only motivation one could have to study math is because it can help us to maximise profit and minimise cost and time. That is a mindset which, unfortunately, is correlated with a certain kind of education, but maybe those high schoolers are still appreciative of something which is a bit more ... like a nice chess problem. Totally useless in budget calculations. – Torsten Schoeneberg Jun 03 '20 at 06:54
@TorstenSchoeneberg: a) your analogy is another distortion; the 7BoK requirement that a bridge can only be crossed once is purely arbitrary, has no real-world motivation and simply means traversal solutions must take >=1 extra link, unlike in chess where material has obvious real-world analogy. b) Your claim "play into the idea that the only motivation... profit, cost, time" is nonsense; we could equally have picked other real-world weights. I said a real motivations beats a bogus motivation, esp. when dealing with HS students, which was, uhh, what the question actually asked about. – smci Jun 03 '20 at 08:06
As neither you nor @HagenvonEitzen point out, the "impossibility result" merely means real traversal solutions do exist, just they will require >= 1 extra step, big deal. This largely stops being surprising the moment we formulate the concept of degree of a node, in the same way that the arcane wonder that 5^2 + 12^2 = 13^2 stops being surprising once we discover the formula to generate all Pythagorean triples (Yes we know 7BoK motivates abstraction to nodes and edges) – smci Jun 03 '20 at 08:17
...and yes I understand the motivation of a hitherto-unseen class of problem, I already acknowledged that is what 7BoK represented waay back in the 1730s. But these days you can pick better examples that both motivate and whose constraints have obvious real-world origins that aren't made-up or silly, yet counterintuitive solutions; the symmetry-breaking aspect of the Minimal Steiner Tree for four points, is one good example. Yaglom and Yaglom is also a superb compendium. – smci Jun 03 '20 at 08:29

score 12 · Answer 2 · answered May 08 '20 at 19:54

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 you know them. You could present them at the top of the talk in a fun way, and use a specific example of a graph $G$ (something simple like a small tree or a cycle). You can even use volunteers from the audience as the two players to demonstrate a sample game.

I also suggest that it's okay to use vague terms like "dots" and "connections" (instead of vertices and edges) to start with. You can introduce the formal terminology as the audience realizes that we need such words to describe some concepts. So, I highly suggest an activity in the middle of the talk where the audience breaks into small groups to play the game with each other. If you haven't already used words like vertex and path and cycle/circuit, the audience will hopefully realize they need them and invent them right there (or you could guide them into doing so).

Specify a graph $G$ to be the playing board. There are two players: a cop and a robber.
The cop gets to choose a vertex to start on.
Knowing the cop's starting location, the robber then gets to choose a starting location.
The cop gets to move first. They may travel along an edge to an adjacent vertex, or they may choose to stay put. They can "see" where the robber is at all times.
The robber gets to move next. Likewise, they may travel along an edge to an adjacent vertex, or they may choose to stay put (and sometimes that is the strategically sound choice). They can "see" where the cop is at all times.
The turns go back and forth like that. If at any point, the cop lands on the robber's vertex, the cop wins. If, instead, the robber can always evade the cop (formally: there exists a winning strategy) then we say the robber wins.

There are some natural questions that arise, and you can pose these in your talk, or work with the audience to come up with them together:

On which graphs $G$ will the cop win? On which will the robber win instead? This question was answered in the early 1980s by Nowakowski & Winkler: https://en.wikipedia.org/wiki/Cop-win_graph You could use simple examples like a tree (cop wins), cycle (robber wins as long as length is at least 4), Petersen graph (robber wins), etc.
Let's say we have a $G$ where we know the cop wins. How many moves will it take? If both sides play optimally, how long can the robber draw out the process of losing? This is the concept of capture time and it has been well studied but there are lots of open problems.
Let's saw we have a $G$ where we know the cop loses. What if we allowed two cops, and they can move independently at the same time? On which graphs will these two cops win? For example, cycles require 2 cops; but something like the Petersen graph requires more than 2.
What if we have more than one cop but we let only one move at a time? (Kinda like chess where you have a team of pieces but can only move one piece per turn.) This is know as the lazy cops variant. Does that change any of the examples in #3 we just explored? For example, cycles still require 2 cops but the capture time will be longer. And some graphs have different results! For example, consider a graph whose vertices are the squares of a $3\times 3$ chessboard and whose edges represent the possible moves of a rook (so vertices are connected by an edge if they're in the same row or column). Then 2 cops can win on this graph, but they both need to be able to move simultaneously; if you only allow one to move at a time, then you need 3 lazy cops to win. Some students and I managed to prove that this graph is, in fact, the smallest possible example of such a phenomenon: https://arxiv.org/abs/1606.08485

score 6 · Answer 3 · answered May 08 '20 at 14:21

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 teaching my 8 year old nephew with a Tinkertoy-like college chem modeling set. This is a topic that he can handle well before having all the grounding of bonding theory, orbitals, etc. He picked it up no problem and now knows more about butanes (two isomers) and pentanes (3 isomers) than 95% of oil and gas executives (who have "NGLs" as one of their income statement items!)

The point (in addition to the cool similarity of chemical isomers and "trees") is that this is an "easy" entree to a tough topic (chemistry) and can be done sans lots of prerequisites. So I LOVE that you are covering graph theory with the kids as it is generally easier--yes, of course, at the real "coal face" of research it's brutal hard and you have to know all sorts of hard stuff. But the neophyte can appreciate a lot of that topic in a way that he could not get much out of say stochastic calculus.

answered May 08 '20 at 14:21

gues

61
1

2

I've upvoted this as it's very useful – but I would say that actually for this particular occasion one of my aims is to include some of the precise terms and symbol soup; if they are considering mathematics (or a course with mathematics component) at university at some point they will need to acquire a taste for it! – dbmag9 May 08 '20 at 15:32
3

I know you want to show "what research is like" and this would dictate showing some of those aspects. But I actually think you should consider to change that objective a bit and be more motivational and exposure-wise. – gues May 08 '20 at 16:41
1

I mean if you want to show what going to a typical research math talk is (which is miserable, as many professional mathematicians can't follow them either), you could do that. But I just don't think that's the right objective or use of the time. The nice, gentle thing about the YT video is that he shows a TINY amount of that dreck, but moves on from it. Seriously, if they want to see how they can get blown away that is easy to do by reading any Wiki math article, which are usually unreadable. – gues May 08 '20 at 16:41
1

I want to show what a typical undergraduate lecture is like; whiteboard work with reasonably careful definitions and propositions. Not miserable, but enough to emphasise that mathematicians use (for example) set notation constantly in order to write concisely. – dbmag9 May 08 '20 at 17:35
@dbmag9: I would say that your inclusion of planar graphs and Euler's theorem is actually not consistent with your claimed goal of desiring precision. The non-planarity of $K_5$ or $K_{3,3}$ is essentially equivalent to the Jordan curve theorem! If you define planarity in terms of having an isomorphic graph that has vertices in the plane and non-crossing line segments for edges, then you will fail to capture the 3-utilities problem as a graph theory problem. This is not at all a coincidence, because it is not a graph theory problem but rather a euclidean topology problem! – user21820 May 10 '20 at 10:43

score 5 · Answer 4 · answered May 08 '20 at 14:08

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.

^{Image from Dan Teague.}

score 5 · Answer 5 · answered May 08 '20 at 19:07

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 moving to a graph of it. Then building theory about all graphs.

I am teaching discrete math. To introduce planar graphs, I actually started with models of platonic solids. (I only had the right polydron pieces to build two of them, and then I grabbed a die for a third. I asked students if there could be more.)

I noticed your title called this a lecture and your text called it a session. The more you can get them to participate and tell you what should happen, the better (ie less lecture, more dialogue and activity). I hope you are able to use this as a chance to inspire.

+1000 for the last paragraph. OP will lose 95% of the students after 5min otherwise. — Eric Duminil, May 09 '20 at 07:45

score 3 · Answer 6 · answered May 09 '20 at 23:40

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 how graph theory is used in GPS systems for navigation, for packet routing on the Internet, and even in video games for path finding.

score 2 · Answer 7 · edited May 11 '20 at 14:55

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, if I have to teach my university class about graph theory, the simple properties of the graph (undirected, directed, connected, fully connected, path etc.) takes up to 15 minutes. So I would cover Dijkstra or Floyd (because way finding in graphs is very important), maybe program a maze solver and be done with it. That gives a quick summary of what graphs are and one specific usage case.

Content for a 40-minute lecture on graph theory for high schoolers

7 Answers7