[tubbzor]

It was always intriguing to me how some popular graph algorithms are rather intuitive, and if left to your own devices and no knowledge of popular approaches you are likely to use some variant of them in problem solving.

One such is constructing a minimum spanning tree. Give them some problem where they would need it on a dense graph and let them struggle to piece it together (and penalize for wrong edges included). At the end you could explain how their strategy related to Prim or Kruskal's algorithms.

Another is finding a shortest path from 1 vertex to another. The context would be rather easy and you could again penalize for an incorrect path taken and let them argue about the optimum route and introduce Dijkstra's at the end.

I think context is the most important thing. No high schooler wants to be given an arbitrary graph and feel like they are doing some mundane problem on it. Put some contextual spin on the problems (perhaps locally relevant) to pique their interest and make it hit home for them as to why these are important problems/solutions.