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.

theprincipal criterion). Students who are having fun are more likely to be inspired to learn. $\endgroup$ – Mark Grant Feb 8 '16 at 10:26