27
$\begingroup$

I have the task of creating a 3rd year undergraduate course in graph theory (in the UK). Essentially the students will have seen minimal discrete math/combinatorics before this course. Since graph theory is not my specialty and I did not take a graph theory course until grad school, I am seeking advice on the content.

I can of course consult excellent books like Diestel's, and numerous online lecture notes, course outlines on university webpages, etc. (although if any of these are particularly great that would be useful to know).

I am also aware of most of the standard results that should go in such a course.

But, what I'm really looking for is, slightly less well known, interesting/fun results that are at the right level to make suitable content (or could be adapted to assignment questions).

So, what is your favourite, unusual fact, that would be suitable for such a course?

Apologies if this is not a suitable question for MO. Let me know and I will delete. I'm aware of the related question Interesting and Accessible Topics in Graph Theory which gave me some good ideas, but was generally aimed at topics for high school students rather than final year undergraduates.

Improve this question
$\endgroup$
10
  • 11
    $\begingroup$ This question is not about math research. It belongs to matheducators.stackexchange.com, please move it there. $\endgroup$
    – Andrej Bauer
    Commented Feb 6, 2016 at 9:27
  • 19
    $\begingroup$ Most questions about teaching (see this tag) are not about research, but about teaching. And I expect more useful advices here on MO, than on matheducators, since people who teach graph theory courses are active rather on MO. $\endgroup$
    – Fedor Petrov
    Commented Feb 6, 2016 at 10:49
  • 13
    $\begingroup$ Why do we need a separate subforum? What is not ok with such questions in the common MO? $\endgroup$
    – Fedor Petrov
    Commented Feb 6, 2016 at 12:27
  • 6
    $\begingroup$ @Fedor Petrov: I made a question on meta whether the question should be reopened. meta.mathoverflow.net/questions/2723/… Personally, I agree with you that the question is on-topic here. $\endgroup$
    – Tony Huynh
    Commented Feb 6, 2016 at 13:10
  • 10
    $\begingroup$ @post.as.a.guest: I would say that yes, fun is a principal criterion (although not the principal criterion). Students who are having fun are more likely to be inspired to learn. $\endgroup$
    – Mark Grant
    Commented Feb 8, 2016 at 10:26

10 Answers 10

Reset to default
13
$\begingroup$

Planar graph duality and its consequences, e.g. that a connected planar graph is Eulerian iff its dual is bipartite, or Hamiltonian iff its dual can be partitioned into two induced trees.

The emergence of the giant component in random graphs. The 0-1 law for first-order properties of random graphs, and its connection to the same properties in the Rado graph.

Or, for something more obscure: the existence of perfect matchings in claw-free graphs and (when applied to line graphs) the existence of partitions of any connected graph with evenly many edges into two-edge paths.

Another is the friendship theorem: if a finite graph has the property that each two vertices have exactly one shared neighbor, then it must have the form of a collection of triangles joined at a shared vertex. It is not true for infinite graphs...

I think the equivalence of treewidth with pursuit-evasion games, and havens as strategies for such games, is also a fun fact, but actually proving any of that in an undergraduate class does not sound like fun.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, the friendship theorem is exactly the sort of thing I was looking for. $\endgroup$
    – user62562
    Commented Feb 7, 2016 at 15:35
9
$\begingroup$

The (finite, simple) graphs with the property that their adjacency matrices have spectral radius less than $2$ are precisely the simply laced Dynkin diagrams $A_n, D_n, E_6, E_7, E_8$. Similarly, the graphs with spectral radius exactly $2$ are precisely the affine simply laced Dynkin diagrams $\widetilde{A}_n, \widetilde{D}_n, \widetilde{E}_6, \widetilde{E}_7, \widetilde{E}_8$. This ties most directly into the McKay correspondence, but also to the classification of simple Lie algebras and other places where ADE classifications appear.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I accidentally came across this amazing comment 8 years after it was posted! What is a good reference for this? I have never seen a connection between spectral radius and Dynkin diagrams before. $\endgroup$
    – apurva n.
    Commented Dec 4 at 2:07
9
$\begingroup$

Chip-firing (aka the sandpile model, though both notions have a plethory of different meanings) and rotor-routing. Some sources (no claim of completeness):

... and many more.

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

Ramsey Theory. I show them the proof that R(3) = 6 in the context of friends and strangers at a party. We talk about $R(k,l)$ and $R(2,k)$ as a sanity check. I prove that $R(k,l) \leq R(k-1,l)+R(k,l-1)$. I get them to find R(3,4). I show them the graph that gives the lower bound for R(4,4), and mention the connection to number theory. So, with the result above, that computes R(4,4). At this point, I show them the famous Erdos quote about R(5) and R(6):

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

At this point I like to either mention Ramsey theory on infinite graphs, talk about the connection to Van der Waerden (on arithmetic progressions) and Hales-Jewett (on hypercubes), or show them Erdos's proof of the exponential lower bound on R(k,k). This last one, via the probabilistic method, is my favorite, and only requires extremely basic probability (namely, the fact that in a finite outcome space, the probability of an event E is strictly positive if and only if there is an outcome in E). It also shows them a non-constructive existence proof, and I think that's very worth seeing.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Just as I was writing this, there was activity on another MO question that I think gives another fun result in graph theory. The result is that, if A is the adjacency matrix of G, then tr($A^3$)/6 counts the number of triangles in G. Somehow I was totally unaware of this result, but I'll bet students would find it very interesting, especially compared to the nested for loops approach to finding how many triangles there are. $\endgroup$
    – David White
    Commented Feb 8, 2016 at 13:39
  • $\begingroup$ thanks - could you link me to the post about the adjacency matrix counting triangles? I'm probably being stupid but I can't spot the relevant post. $\endgroup$
    – user62562
    Commented Feb 8, 2016 at 18:05
  • 1
    $\begingroup$ mathoverflow.net/questions/104415/… $\endgroup$
    – David White
    Commented Feb 9, 2016 at 4:29
6
$\begingroup$

Transfer matrix method. Here are some illustrating slides:

http://www.math.ucsd.edu/~gptesler/184a/slides/184a_ch10.3slides_14-handout.pdf

http://www.uwyo.edu/moorhouse/slides/transfer.pdf

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

A couple consequences of Euler's formula $V-E+F=2$ for graphs that can make for nice series of homework exercises:

  • Predict the structure of Buckminsterfullerenes. Carbon tends to form 5 and 6 member rings, so you can model Buckyballs as convex polyhedra whose faces are all pentagons and hexagons. Using Euler's formula, you can show that all such polyhedra must have exactly $12$ pentagons.
    If you assume the additional fact from chemistry that structures with adjacent pentagonal rings are unstable (due to bond strain along the common edge), you can say that any polyhedron not violating this "isolated pentagon rule" must involve at least $60$ carbon atoms, and describe the structure of the only one with $60$ atoms. This turns out to be exactly the structure of the first buckyball discovered.

  • Various results involving the sums of angles. For example, you can use Euler's formula to show that a triangulation of an $n$ sided polygon has $n-2$ triangles, and get the familiar formula for the sum of the angles. From this, a double counting argument, and another application of Euler's formula you can show Descartes rule of angular defect (if the discrepancy at a vertex is $2 \pi$ minus the sum of the angles of each face at that vertex, the sum of the discrepancies of any convex polyhedron is $4 \pi$)

Improve this answer
$\endgroup$
4
$\begingroup$

hI am in the same boat as you, user62562. I am now a bit more than half-way through my first time teaching this 10 week class now. I have 24 students. The most fun I had -and I think the class -- was (A) showing them the spectral algorithms underlying Google's PageRanker uses when we enter searchers following this 5 page article: http://www.ams.org/samplings/feature-column/fcarc-pagerank and (B) teaching them an amazing formula for the number of spanning trees in a connected graph. This number equals any one of the $n^2$ cofactors of that graph's Laplacian. See Biggs, Algebraic Graph Theory, Part 1, section 6.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, pagerank is often the first example I give for why students should care about graph algorithms. As for counting spanning trees, it's called the matrix-tree theorem or Kirchoff's theorem; see also en.wikipedia.org/wiki/Kirchhoff%27s_theorem $\endgroup$
    – David Eppstein
    Commented Feb 10, 2016 at 19:23
3
$\begingroup$

The fact that every planar graph is 4-colorable is certainly beyond the scope of an introductory course, but showing that every planar graph is 5-colorable is certainly doable.

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

Another interesting consequence of Euler's formula $V-E+F=2$ might include a proof that there are exactly five Platonic solids. Given that there are regular polygons with any number of sides, it often comes as a surprise to students that there are only a finite number of regular polyhedra.

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

A concrete and fun problem: Draw $n$ circles (can be intersecting). This divides the plane into regions. Show that this map is two-colorable.

Improve this answer
$\endgroup$

You must log in to answer this question.

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