34
$\begingroup$

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope to use graph theory as a vehicle by which to convey a sense of developing "advanced" mathematics (remember, these students will have seen first-year calculus, at best).

What are you favorite interesting and accessible nuggets of graph theory?

"Interesting" could mean either the topic has a particularly useful application in the real-world or else is a surprising or elegant theoretical result. An added bonus would be if the topic can reveal gaps in our collective knowledge (for example, even small Ramsey numbers are still not known exactly). "Accessible" means that a bright, motivated student with no combinatorial background can follow the development of the topic from scratch, even if it takes several lectures.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ More a suggestion than an answer: spend half a session highlighting the similarities and differences between theory of finite graphs and theory of infinite graphs. If you want an interesting tangent, the elementary first order theory of graphs is finitely axiomatizable and undecidable. This makes it handy to interpret into other theories to show those other theories are undecidable. Edited carefully, this tangent could be made accessible to your audience. Gerhard "Ask Me About System Design" Paseman, 2011.05.10 $\endgroup$
    – Gerhard Paseman
    Commented May 10, 2011 at 20:48
  • 2
    $\begingroup$ Thanks for the many great suggestions. Reading all these has caused me to think that I could potentially structure the course in such a way as to introduce the widest number of adjectives that can precede "graph theory" or "combinatorics". For example, I see in the topics presented here: enumerative, extremal, geometric, computational, probabilistic, algebraic, and constructive (for lack of a better word - I'm referring to things like designs). As a sort of subquestion restricted to the comments, what other adjectives might I attempt to incorporate? $\endgroup$
    – Austin Mohr
    Commented May 14, 2011 at 5:24
  • $\begingroup$ applied. Gerhard "Ask Me About System Design" Paseman, 2011.05.16 $\endgroup$
    – Gerhard Paseman
    Commented May 16, 2011 at 20:06
  • $\begingroup$ @Austin: It would be nice if you let us know what you decide to teach, and how it goes this summer! $\endgroup$
    – Joseph O'Rourke
    Commented May 19, 2011 at 23:34
  • $\begingroup$ I always though it would be nice to give an exposition of the Road coloring theorem, sort of as a "universal" directions theorem (to a party, perhaps). It has plenty of real-world applications. But I think the proof is too difficult. $\endgroup$
    – Steve D
    Commented Apr 30, 2012 at 11:05

18 Answers 18

Reset to default
22
$\begingroup$

I have found that the Art Gallery Problem engages middle- and high-school students, and quickly leads to the unknown, which itself can be eye-opening to students. (On the latter point, students tend to think of mathematics as settled, so it is nice for them to reach unsolved problems they can comprehend, which abound at the interface between geometry and graph theory.) Proving the traditional art gallery theorem (that $\lfloor n/3 \rfloor$ guards suffice and are sometimes necessary to cover an $n$-wall gallery) introduces triangulations and the chromatic number of a graph. There are many sources, including the recent book (if I may self-promote) Discrete and Computational Geometry.

                3-coloring

Addendum. May I also recommend "How to Guard an Art Gallery and Other Discrete Mathematical Adventures", by T.S. Michael, whom I had the pleasure of teaching two decades before his book was published.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ May I chime in that Joseph's Art Gallery Theorems and Algorithms, though not as recent, remains nice to read. $\endgroup$
    – J. M. isn't a mathematician
    Commented May 10, 2011 at 12:56
  • 1
    $\begingroup$ Steve Fisk has a beautiful solution to this problem, which I think might be accessible enough for Austin's purposes. But I'm biased because Fisk was a professor of mine in undergrad and died not too long ago. I've been thinking of giving a seminar talk on this theorem as a tribute. $\endgroup$
    – David White
    Commented May 10, 2011 at 18:51
  • 1
    $\begingroup$ @David: Steve will live on through his beautiful proof! $\endgroup$
    – Joseph O'Rourke
    Commented May 19, 2011 at 23:43
13
$\begingroup$

Matching theory. This includes Hall's marriage theorem, Tutte's theorem and the Gale-Sharpley stable matching theorem.

One reason to teach this subject to undergrads is that it changes the way mathematicians think about algorithms. The standard algorithms one learns in high school and undergraduate studies (Dijkstra algorithm, quicksort and the likes, etc.) are all generally looked down on by mathematicians, as they (1) seem to be just particularly efficient methods to compute some objects which are already clear to exist, (2) are usually of low complexity (much lower than that of proofs in undergraduate mathematics), (3) add no theoretical value (in fact they do, but algorithmic content in mathematical proofs is often cleverly hidden by whoever writes up the proof, so it looks like they don't). In contrast, the perfect matching algorithm (by using augmenting paths) and the Gale-Sharpley algorithm are rather nontrivial and actually are major components in the proofs of the existence of perfect matchings rsp. stable matchings.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If you're covering matching theory, I would add König's theorem (in a bipartite graph max matching + max independent set = #vertices), the theorem that a regular bipartite graph has a perfect matching, and Petersen's theorem that a bridgeless cubic graph has a perfect matching (e.g. a triangulated 2-manifold has a matching of its triangles). But I have to admit that last week in the matching part of my graph algorithms class I covered only König and Gale–Shapley because it's about graph algorithms not graph theory and I needed the remaining lecture time to cover the Hopcroft–Karp algorithm. $\endgroup$
    – David Eppstein
    Commented May 11, 2011 at 4:29
10
$\begingroup$

Planar graph duality. E.g. the facts that

  • A set of edges forms a connected spanning subgraph of a planar graph G if and only if the complementary set of edges forms an acyclic subgraph of the dual, and vice versa.
  • Since spanning trees are just connected acyclic subgraphs, it follows that a subgraph is a tree if and only if its complement is dual to a tree. Euler's formula follows immediately.
  • The edges that are not in the minimum spanning tree of a planar graph G are the duals of the edges that are in the maximum spanning tree of its dual.
  • A planar graph is bipartite if and only if its dual is Eulerian.
  • A planar graph is 3-connected (polyhedral) if and only if its dual is.
  • The graphic matroid of a planar graph is the dual of the graphic matroid of the dual graph. Planar graphs are the only graphs for which the dual of the graphic matroid is also graphic.
  • A directed planar graph is acyclic if and only if its dual graph (with the dual edges oriented 90 degrees clockwise from the primal ones) is strongly connected.
Improve this answer
$\endgroup$
2
  • $\begingroup$ One could make an interesting module on Euler's formula alone, following David's 19(!) proofs of Euler's theorem: ics.uci.edu/~eppstein/junkyard/euler $\endgroup$
    – Joseph O'Rourke
    Commented May 10, 2011 at 12:25
  • $\begingroup$ Thanks! Your comment reminds me that I need to update that site: there are a couple more proofs I've encountered (one in my own latest SoCG paper) that I haven't yet added. $\endgroup$
    – David Eppstein
    Commented May 10, 2011 at 21:26
10
$\begingroup$

One problem that I found quite interesting is the Hadwiger-Nelson problem for coloring the plane. The proofs that the answer is at most $7$ and at least $4$ are easy and elegant (but also quite different), and it has the added bonus that it is an open problem.

Edit: The chromatic number is now known to be at least 5.

Improve this answer
$\endgroup$
0
8
$\begingroup$

The "$-1$ colors" theorem. This allows you to talk about coloring, about chromatic polynomials, and (for example) about hyperplane arrangements, their chambers and so on (Orlik+Terao's book on hyperplane arrangements has the details)

Doing everything in detail is a bit of work, but you probably don't need that.

Everyone with appreciation for beautiful math should fall for this!

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you provide an introductory link, please? $\endgroup$
    – Hans-Peter Stricker
    Commented Aug 15, 2012 at 20:28
  • $\begingroup$ The book by Orlik and Terao is quite accessible in fact. Richard Stanley has notes on his webpage on the subject, if I recall correctly. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Aug 15, 2012 at 23:26
7
$\begingroup$

Coloring problems are beautiful and accessible. If you're mentioning Ramsey numbers (as you should!), it will be easy to segue into coloring problems (or vice versa).

Some topics worth including would be

  • Bipartite iff 2-colorable
  • Four/Five Color Theorems
  • Chromatic number, basic bounds
  • Edge chromatic number, Vizing's Theorem, König's Line Coloring Theorem

These were some of my favorite results in my first graph theory course.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You beat me to it! I was going to say the four/five color theorem since this year, for a high school math circle ran at UBC, we had a lecture which stated the four color theorem, and proved the five color theorem. It went very well, and the students enjoyed it. $\endgroup$
    – Eric Naslund
    Commented May 10, 2011 at 20:59
7
$\begingroup$

Here is a topic that he kept me wasting (?) many hours: there is a theorem that every embedding in 3-space of $K_7$ , the complete graph on 7 vertices, contains a knot. Draw such an embedding and find the knot(s)!

Every embedding of $K_6$ contains a link, but that is usually much easier to find.

If I can find the reference, I'll add that as a comment.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The reference is Conway, J. H.; Gordon, C. McA. Knots and links in spatial graphs. J. Graph Theory 7 (1983), no. 4, 445–453. The proof of the first statement is interesting: they prove that the product of the Arf invariants of all embedded circles in the embedded $K_7$ is invariant under Reidemeister moves of the embedding. So only one example is needed! $\endgroup$
    – Ronnie Brown
    Commented Jan 13, 2012 at 23:10
6
$\begingroup$

1) As you say in the question, Ramsey numbers, both the (easy) upper bound - an elegant example of the power of combinatorics - and the lower bound, one of the rare proofs that is easy, short, and completely surpising.

2) Turan's theorem about the size of independent sets in graphs. Again, an easy application of the probabilistic method (though you don't even need the language of probability to state it). It's also interesting that this is an example, unlike Ramsey numbers, where the 'easy' proof actually gives the best possible bound (for general graphs).

Of course given the wide variety of problems graphs are applicable to, it's useful to be able to detect structured subgraphs, either complete graphs or independent sets. These are also good examples of non-constructive proofs.

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

I think that presenting the connection between random walks and electrical networks (like in the classic text "Random walks and electric networks" by Doyle and Snell) is an interesting and feasible idea. Just a week ago I taught a 6-day course about this to talented high schoolers and it worked out very nicely. It's a good opportunity to show them interesting applications of probability and give a flavour of a vibrant field of mathematics. Plus, there is a quite a lot of room for digressions on Markov chains, spectral graph theory etc.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I don't know how feasible it'll be to talk about spectral graph theory to students who may not have seen linear algebra before... $\endgroup$
    – Qiaochu Yuan
    Commented May 10, 2011 at 9:51
  • $\begingroup$ Of course you can't treat this topic extensively, but mentioning expanders, the fact that their geometric properties are connected to the mixing rate of the random walk and can be analyzed algebraically is surely doable as a digression (as well as things like PageRank or random graphs). $\endgroup$
    – Michal Kotowski
    Commented May 10, 2011 at 15:33
3
$\begingroup$

This is probably not what you're looking for, but if I were teaching such a course I'd focus on the interplay between algorithms for various graph problems and the more traditional mathematical approach of proving theorems in graph theory.

For example, you can prove the "max flow-min cut" theorem by developing an algorithm that simultaneously finds a maximum flow and a corresponding min-cut.

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

I think the graph isomorphism problem is a good choice: it's a fundamental question and a good lead in to the notion of isomorphic and some complexity theory---it's not known if it's NP-complete. This should be doable in a couple of lectures, depending on how thorough you want to be.

There are also applications, but I'm not the one to tell you about them.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The question is: what interesting theorems does this subject contain? As far as I understand, it's all open problems. $\endgroup$
    – darij grinberg
    Commented May 10, 2011 at 8:59
2
$\begingroup$

Some very accessible and interesting content that I think would cause a positive impression can be found in the book "Graphs and their uses" by Oystein Ore.

If I was to give an introductory course on graph theory for such an audience, I would follow part of this book at the beginning and then I would complement with something else. I would start with a classic problem: is it possible to connect through paths in the plane each one of three wells to each one of three different houses without intersections? There is a very neat and elementary explanation on why this is not possible that only uses the Jordan's curve theorem.

After mentioning other classic examples such as the Königsberg bridge problem (and the criterion to find eulerian paths in a graph) and hamiltonian cycles (stressing the lack of an efficient general method to find these), I would move to a remarkable fact that is sometimes known as the "sports journalist paradox", according to which is quite common to find, in some sports tournaments where each team plays against each other, an oriented cycle that involves all teams; in other words, team A wins team B, which wins team C, and so on...till some team in the chain wins team A! It is not difficult to characterize when we can find such a behaviour, and the answer turns out to be quite often!

I would then mention map coloring, and give a complete proof of the five color theorem. But most important, I would discuss Euler's formula for poligonal nets and how to apply it to characterize all platonic solids. This achievement, while elementary, could be a nice way to keep the audience interested and pave the way to further deeper results.

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

It seems to me that your goal should be to give them some elementary results with proofs (so they get used to that type of thinking) but also some high-level, cool, and surprising results to whet their appetite for more. In studying planarity you can find many cool and surprising results. I took a course from Laszlo Lovasz on such topics a few years ago, and he put his lecture notes online. You can link to them from this site: http://www.cs.elte.hu/~lovasz/geomgraph.html

Highlights I think high school students could understand and enjoy (perhaps skipping some of the proofs):

  • Section 1.1. Kuratowski's Theorem: A graph $G$ is embeddable in the plane if and only if it does not contain a subgraph homeomorphic to the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$.
  • Section 1.3. Steinitz's Theorem: A simple graph is isomorphic to the skeleton of a 3-polytope if and only if it is 3-connected and planar.
  • Section 2.1. Unit Distance Graphs
  • Chapter 4. Turning the edges of $G$ into rubber-bands and talking about when they find equilibrium in the form of a planar representation of $G$

Finally, Chapter 6 has some really amazing results:

  • The Cage Theorem: Every 3-connected planar graph is isomorphic to the 1-skeleton of a convex 3-polytope such that every edge of the polytope touches a given sphere.
  • Koebe's Theorem: Let $G$ be a 3-connected planar graph. Then one can assign to each node $i$ a circle $C_i$ in the plane so that their interiors are disjoint, and two nodes are adjacent if and only if the corresponding circles are tangent.
Improve this answer
$\endgroup$
2
$\begingroup$

Take a look at my graph theory site, http://mathcove.net/petersen and let me know if the Petersen program would be useful. I would be willing to grant you a free license. Chris Mawata

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

How about graphic sequences? This might be a nice introduction to the world of inverse problems - an important concept of whose existence most high school curricula wouldn't even hint.

Improve this answer
$\endgroup$
1
$\begingroup$

I'd suggest Turán's theorem, the bonus being the somehow surprising hardness of the corresponding problem for 3-uniform hypergraphs.

Improve this answer
$\endgroup$
1
$\begingroup$

On the application side, you can introduce graph theory as a way to model connected systems:

  • web pages (familiar, has some nice visualizations, but hard to get your hands on),
  • people a la Stanley Milgram and "six degrees of separation" (important but very "fuzzy"),
  • actors connected by movies (precise via the Internet Movie Database and front-end Oracle of Bacon -- for ideas on using this, see my PRIMUS article "Kevin Bacon and Graph Theory," available through my web page)
Improve this answer
$\endgroup$
2
  • $\begingroup$ There are some nice pictures here, but any actual mathematical theorems? $\endgroup$
    – darij grinberg
    Commented May 10, 2011 at 9:00
  • $\begingroup$ Nope, no theorems in these initial applications. Their purpose is to engage students early on and give contexts for distance, cliques, diameters, dynamic graphs, etc. I like theorems as well as the next mathematician, but they're not the only possible "nuggets." $\endgroup$
    – Brian Hopkins
    Commented May 11, 2011 at 3:01
1
$\begingroup$

I believe the book

Hajnal Péter: Gráfelmélet. 1997, Polygon, Szeged.

is an extended answer to exactly this question. (There's a second edition from 2003, but apparently no translations to other languages.)

The writing style of this book makes it accessible to high school students (as opposed to the Lovász book whose concise style makes it ideal for research mathematicians). Thus, most of the material is accessible at high school level, while at the same time the book covers so many difficult topics that it'd be difficult to cover all the proofs even in a semester long high school course.

The book remains a useful reference for BSc combinatorics exams (not alone though, because some necessary topics are missing).

Here are some of the topics included (many of these were mentioned in other responses).

  • Flow-cut theorem and algorithm, Menger's theorems, Kőnig-Hall, maximal matching algorithm for bipartite graphs, Tutte's theorem, and even Edmond's algorithm to find maximal matching in any graph.
  • Euler circuits, then Dirac's sufficient condition for Hamiltonian circuit
  • Graph coloring, Brooks' theorem (when a graph's chromatic number reaches its maximum degree), high chromatic graphs without triangle, Hajós's characterisation of graphs with chromatic number (exercise 9.16 in Lovász), Vizing's theorem on edge coloring,
  • Turán's theorem, Erdős-Stone theorem about the asymptotic on the number of edges of a graph not containing a particular non-bipartite graph, asymptotic for $ C_4 $-free graphs.
  • Ramsey theorems.
  • Complexity theory results about graph problems, including Karp reductions between Hamiltonian circuits and chromatic number and independence number. Does not include the Cook-Levin theorem so no problem is actually proven to be NP-complete.
  • Planar graphs, duality, Whitney-duals, Euler's theorem, Kuratowski's theorem on the characterization of planar graphs (yes, with a proof), Robertson and Seymour's graph minor theorem without proof, the four color theorem without proof, the five color theorem and Kempe's proof, Hadwiger's conjecture.
  • Perfect graphs, Lovász's theorem on the complement of perfect graphs (yes, with a proof), comparability graphs of posets are perfect.

Note finally that before any topic, you'd need to cover some of the first chapter which introduces basic terminology about graphs, which is important to plan if you are giving only a few lectures. (Have you told us about the total length of lectures you are planning to give?) Edit: ah, I see the lectures the question is referring to are now in the past, so there's no point to ask such a concrete question.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .