I was talking recently with my daughters about non-planar graphs, like $K_{3,3}$, $K_5$, and the 7 bridges of Königsberg. They got pretty interested in it. Then we tried to dive into the Petersen graph and the concept of linkless embedding in 3 dimensions. This wasn't so successful.
The idea of planarity can be illustrated pretty well on paper, but in 3 dimensions, one needs some sort of modeling toy to show what we're talking about in terms of vertices and edges that link together in cycles.
There are face-oriented toys out there for exploring geometry in 3D, like these which allow you to build certain polyhedra by attaching rigid triangular and square faces to each other edge-to-edge.
There are also rigid edge-oriented toys, like this one (unavailable), which offer more freedom in arrangement of vertices and edges.
But if we want to explore graph theory in a way that's not limited to edges that are all straight and all the same length, what are some good options?
This flexible rod play set would work, I suppose, though the joints supplied don't look very much like vertices. Something cheap would be nice. Pipe cleaners and clay seem to be a popular approach, but I wonder what kind of clay is stiff enough to maintain a 3D configuration of more than a few vertices. Pipe cleaners stuck into little foam balls? Any better ideas? They don't have to be brightly-colored pieces that are marketed as toys.
For exploring polyhedra, one "toy" that I really love is Zometool. A really cool think about it is that the colored edges are all different lengths from each other and plug into specific spots in the vertex balls. So it's much easier to see how to create regular polyhedra and explore the lengths between vertices. (Alas, you need the green strut add-ons to make all the platonic solids, but I'll recommend it all the same.)