Some very accessible and interesting content that I think would cause a positive impression can be found in the book "Graphs and their uses" by Oystein Ore.

If I was to give an introductory course on graph theory for such an audience, I would follow part of this book at the beginning and then I would complement with something else. I would start with a classic problem: is it possible to connect through paths in the plane each one of three wells to each one of three different houses without intersections? There is a very neat and elementary explanation on why this is not possible that only uses the Jordan's curve theorem.

After mentioning other classic examples such as the Königsberg bridge problem (and the criterion to find eulerian paths in a graph) and hamiltonian cycles (stressing the lack of an efficient general method to find these), I would move to a remarkable fact that is sometimes known as the "sports journalist paradox", according to which is quite common to find, in some sports tournaments where each team plays against each other, an oriented cycle that involves all teams; in other words, team A wins team B, which wins team C, and so on...till some team in the chain wins team A! It is not difficult to characterize when we can find such a behaviour, and the answer turns out to be quite often!

I would then mention map coloring, and give a complete proof of the five color theorem. But most important, I would discuss Euler's formula for poligonal nets and how to apply it to characterize all platonic solids. This achievement, while elementary, could be a nice way to keep the audience interested and pave the way to further deeper results.