13
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Rusty Core
    May 8, 2020 at 23:00
  • 2
    $\begingroup$ Perhaps you'll find chapter 4 of Discrete Mathematics, by Oscar Levin, helpful: discrete.openmathbooks.org/dmoi3/sec_gt-intro.html $\endgroup$
    – Sue VanHattum ♦
    May 9, 2020 at 0:33
  • $\begingroup$ @SueVanHattum I came across that while pursuing some of the ideas from the answers here and have found it extremely useful! $\endgroup$
    – dbmag9
    May 9, 2020 at 10:13
  • $\begingroup$ @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. $\endgroup$
    – dbmag9
    May 9, 2020 at 10:14
  • $\begingroup$ 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. $\endgroup$
    – xdhmoore
    May 10, 2020 at 4:00

7 Answers 7

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
17
  • 28
    $\begingroup$ @smci: "Seven bridges of Königsberg problem is boring and toy". Right. Only an idiot like Euler would write a paper about it. $\endgroup$
    – Torsten Schoeneberg
    May 9, 2020 at 1:59
  • 12
    $\begingroup$ 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 $\endgroup$
    – Hagen von Eitzen
    May 9, 2020 at 10:03
  • 8
    $\begingroup$ @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 $\endgroup$
    – Hagen von Eitzen
    May 9, 2020 at 10:08
  • 3
    $\begingroup$ @TorstenSchoeneberg I joined this community specifically to upvote that comment! $\endgroup$
    – Avrohom Yisroel
    May 10, 2020 at 16:48
  • 5
    $\begingroup$ 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. $\endgroup$
    – WoJ
    May 10, 2020 at 20:03
12
$\begingroup$

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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
Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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! $\endgroup$
    – dbmag9
    May 8, 2020 at 15:32
  • 3
    $\begingroup$ 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. $\endgroup$
    – gues
    May 8, 2020 at 16:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – gues
    May 8, 2020 at 16:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – dbmag9
    May 8, 2020 at 17:35
  • $\begingroup$ @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! $\endgroup$
    – user21820
    May 10, 2020 at 10:43
5
$\begingroup$

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.

          DanTeague
          Image from Dan Teague.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ +1000 for the last paragraph. OP will lose 95% of the students after 5min otherwise. $\endgroup$
    – Eric Duminil
    May 9, 2020 at 7:45
3
$\begingroup$

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.

enter image description here

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.