What (fun) results in graph theory should undergraduates learn? 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.
 A: 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.
A: Chip-firing (aka the sandpile model, though both notions have a plethory of different meanings) and rotor-routing. Some sources (no claim of completeness):


*

*Alexander E. Holroyd, Lionel Levine, Karola Meszaros, Yuval Peres, James Propp, David B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, arXiv:0801.3306. If you only have time for one source, then this should probably be it; it contains most of the "fun results", including the fact that chip-firing stabilizes (when there is a sink) and the final result does not depend on the path taken.

*Anders Björner, László Lovász, Chip-firing games on directed graphs and Anders Björner, László Lovász, P. W. Shor, Chip-firing games on graphs. These older works have remarkably little intersection with the previous one; they focus more on the use of greedoids and the relations to spectral graph theory.

*Benjamin Bond, Lionel Levine, Abelian networks, trilogy: part I (arXiv:1309.3445), part II (arXiv:1409.0169), part III (arXiv:1409.0170). This is a vast generalization, which is probably too abstract and notation-heavy for undergrads, but it really seems to bring out the real ideas behind the material.

*Bálint Hujter, Lilla Tóthmérész, Chip-firing based methods in the Riemann--Roch theory of directed graphs, arXiv:1511.03568. A new approach to the "discrete Riemann-Roch theory" of sandpiles on graphs. See also the references therein, as they occasionally give more elementary proofs.

*Tian-Yi Jiang, Ziv Scully, Yan X Zhang, Motors and Impossible Firing Patterns in the Parallel Chip-Firing Game, arXiv:1211.6786. This is about a deterministic variation of the chip-firing game: All vertices have to fire as soon as they can, not just when they decide to. Corollary 7.1 is a beautiful result that, to my knowledge, has not received the nice proof it deserves (the proof given in the paper involves checking that a weighted graph with 64 vertices and 256 edges has no negative-weight cycles).

*Scott Chapman, Rebecca Garcia, Luis David García-Puente, Martin E. Malandro, Ken W. Smith, Algebraic and combinatorial aspects of sandpile monoids on directed graphs, arXiv:1105.2357.

*László Babai, Evelin Toumpakari, A Structure Theory of the Sandpile Monoid for Directed Graphs, REU 2010 paper.

*Eric Goles, Michel Morvan, Ha Duong Phan, Sandpiles and order structure of integer partitions. This relates chip-firing to the dominance order on partitions (don't ask me how).
... and many more.
A: 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
A: 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$)
A: 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. 
A: 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.  
A: 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.
A: A concrete and fun problem: Draw $n$ circles (can be intersecting). This divides the plane into regions. Show that this map is two-colorable. 
A: 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.
A: 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. 
