Integrating Graph Theory into AP CS A
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)