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.
Best Answer
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.