I'm very surprised that we don't teach basic graph theory in <= high school education. It has such a nice, gradual slope from puzzles and pictures to proofs, algorithms, and all sorts of science. I've done activities/lectures on the topic to all levels of high school (some with notes [1]), and it is routine to see amazement and engagement. And Hamkins shows it can go all the way down to eight-year-olds. It seems like a win-win to include it in every math teacher's repertoire. It can go as deep as the students want it to go.
[1]: http://jeremykun.com/2011/06/26/teaching-mathematics-graph-t...