I'm firmly convinced that graph theory is a perfect subject to teach to young (primary school) children. It allows an introduction to core aspects of mathematics - abstraction, generalisation, formalism, proof - in a context where there's a concrete visual representation and without requiring significant prerequisite knowledge. It offers the possibility of building to more difficult material (matchings, Ramsey numbers) and methods and tools (variables, induction, reductio), but also a range of topics which can be introduced independently at a low level of complexity (graph colouring, paths, simple functions).
Graph theory is not dependent on the arithmetic or geometry that's in primary school curricula - students need to be able to do elementary arithmetic, but certainly don't need long division, fractions, or even times tables. It's also rather different in feel, so potentially not just "extension" material for the students who have no trouble with the standard curriculum, but a way of inspiring children who are unexcited by (or even hostile to) that. (One wouldn't even need to tell the children it was mathematics - it could just be introduced as "graph theory".)
Helen's first contact with graph theory came quite accidentally a year ago. I was reading the chapter on graph theory in Stilwell's Mathematics and Its History when she asked what I was reading... the Kuratowski Theorem, so I explained complete graphs such as K₅ (5 vertices with all possible edges between them) and then complete multipartite graphs such as K₂,₃ (all possible edges between groups of size 2 and 3, but no edges within those groups). These are basically functions, taking one or more integers as input and giving graphs as output. She thought that was fun, and I've found her amusing herself by drawing complete multipartite graphs. (A few months later we had a serendipitous encounter with random graphs, but that's a bit out of the way in any sensible introduction to graph theory.)
Maybe six months ago I gave her a proper definition of a (simple) graph, and explained the concepts of order (the number of vertices) and size (the number of edges). We looked at some examples such as |P₃| = 2 and |K₄| = 6 and I used this as an opportunity to introduce variables, in this case in the equation |Pₙ| = n-1, and she seemed to understand that. (But an attempt to introduce proof by induction was probably a step too far.)
Then for a school Science Day in February I scrambled to put together a (not used in the end) workshop, based around Joel Hamkin's pamphlet "Graph Coloring and Chromatic Numbers". Helen had no trouble with that, and seems comfortable with chromatic numbers (the smallest number of colours needed to colour a graph's vertices so no adjacent ones have the same colour) and the statement of the Four Colour Map Theorem. She even seems to understand the equivalency of maps and planar graphs (not in the pamphlet, but I threw it in). And we've just started on the second part of the pamphlet, on Eulerian paths and circuits.
What to tackle next? One obvious candidate is Hamkin's other pamphlet, on Euler's formula. Then there are Hamiltonian paths and tours. And the concepts of distance and diameter are not hugely complex but the latter would introduce basic min-max logic (the distance between two vertices is the length of a shortest path connecting them, while a graph's diameter is the greatest distance between any two vertices).
I'm seriously contemplating writing a "graph theory for primary schools" book. Would anyone like to collaborate with me on that? It would be crucial to include enough background to bring teachers up to speed on a subject that's likely to be unfamiliar to them, as well as worksheets that could be copied and handed out to the students, so my ideal collaborator would probably be a teacher rather than a mathematician.