Integrating Graph Theory into AP CS A During our year-end exit interviews with our outgoing seniors, the students made an explicit request to include some graph theory within our curriculum.  This seems like an excellent idea, but the only place where we can fit it is in AP CS A1.

Obviously, graph theory is not within the AP curriculum per se, but I wonder if there is some way to shoe-horn at least a bit of it into a lab somewhere.  Even so, I am having trouble finding a spot within the AP curriculum.  Obviously, AP CS A focuses a great deal on arrays, loops, and objects.  There's not a heavy emphasis on recursion (though it is present).  Is there somewhere where graph theory can find some kind of "fit" within an AP class?

1 I'm unable to find a clean, succinct list of topics covered in AP for those unfamiliar, but this teacher's site has a list of unit headings that could serve as a very quick overview.
You may very well have some examples where you can discuss state machines and hence state diagrams, that is, graphs. 

For example, if you're creating a game with a computer controlled character, that character might be in different states: pursue, search, attack &lt;-- you can introduce a graph representing the states and transitions.

I wrote about this a bit here: https://cestlaz.github.io/posts/2012-12-17-layers-of-a-lesson.html

If you have a class that goes beyond the APCS-A curriculum and do more recursion, you can look at a maze solver (as I do), knights tour, etc - this lets you discuss searching the state space graph - DFS (and allude to alternatives including heuristic search and such), paths, etc. You can also talk about circuits and cycles (knights tour variants)