I study pursuit-evasion games on graphs, so I will recommend using the cops & robbers game as a way to introduce graph theoretic terminology, concepts, and examples. It should also keep the tone informal and recreational, which will do far more (I believe) to actually inspire the students to study more mathematics.
Below are the rules of the game, so you know them. You could present them at the top of the talk in a fun way, and use a specific example of a graph $G$ (something simple like a small tree or a cycle). You can even use volunteers from the audience as the two players to demonstrate a sample game.
I also suggest that it's okay to use vague terms like "dots" and "connections" (instead of vertices and edges) to start with. You can introduce the formal terminology as the audience realizes that we need such words to describe some concepts. So, I highly suggest an activity in the middle of the talk where the audience breaks into small groups to play the game with each other. If you haven't already used words like vertex and path and cycle/circuit, the audience will hopefully realize they need them and invent them right there (or you could guide them into doing so).
- Specify a graph $G$ to be the playing board. There are two players: a cop and a robber.
- The cop gets to choose a vertex to start on.
- Knowing the cop's starting location, the robber then gets to choose a starting location.
- The cop gets to move first. They may travel along an edge to an adjacent vertex, or they may choose to stay put. They can "see" where the robber is at all times.
- The robber gets to move next. Likewise, they may travel along an edge to an adjacent vertex, or they may choose to stay put (and sometimes that is the strategically sound choice). They can "see" where the cop is at all times.
- The turns go back and forth like that. If at any point, the cop lands on the robber's vertex, the cop wins. If, instead, the robber can always evade the cop (formally: there exists a winning strategy) then we say the robber wins.
There are some natural questions that arise, and you can pose these in your talk, or work with the audience to come up with them together:
- On which graphs $G$ will the cop win? On which will the robber win instead? This question was answered in the early 1980s by Nowakowski & Winkler: https://en.wikipedia.org/wiki/Cop-win_graph You could use simple examples like a tree (cop wins), cycle (robber wins as long as length is at least 4), Petersen graph (robber wins), etc.
- Let's say we have a $G$ where we know the cop wins. How many moves will it take? If both sides play optimally, how long can the robber draw out the process of losing? This is the concept of capture time and it has been well studied but there are lots of open problems.
- Let's saw we have a $G$ where we know the cop loses. What if we allowed two cops, and they can move independently at the same time? On which graphs will these two cops win? For example, cycles require 2 cops; but something like the Petersen graph requires more than 2.
- What if we have more than one cop but we let only one move at a time? (Kinda like chess where you have a team of pieces but can only move one piece per turn.) This is know as the lazy cops variant. Does that change any of the examples in #3 we just explored? For example, cycles still require 2 cops but the capture time will be longer. And some graphs have different results! For example, consider a graph whose vertices are the squares of a $3\times 3$ chessboard and whose edges represent the possible moves of a rook (so vertices are connected by an edge if they're in the same row or column). Then 2 cops can win on this graph, but they both need to be able to move simultaneously; if you only allow one to move at a time, then you need 3 lazy cops to win. Some students and I managed to prove that this graph is, in fact, the smallest possible example of such a phenomenon: https://arxiv.org/abs/1606.08485