Maybe this isn't exactly graph theory but it is kind of combinatorial...

You could talk about the 5 platonic solids (someone in your department may have models of these sitting around). Discuss the orbit-stabilizer theorem and then use it to count the number of (rotational) symmetries of the solids. I find that most people are surprised to find out that counting the rotational symmetries of the dodecahedron is as simple as "12 faces times 5 rotations fixing a face = 60 rotational symmetries"