What (fun) results in graph theory should undergraduates learn?

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.

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.

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.