[maddening]

If something is intuitive only at the end of 4-5 month long course, it is not intuitive and I would not show it during any sort of "introduction to...". Definition requiring former explanation of a whole graph theory would be something I would put at the end... of an article about graph theory. I cannot make many assumptions about my readers, and CS magna cum laude graduate is definitely not one of them (why would they need the article then?).

[soVeryTired]

You don't need a massive amount of graph theory. "Rearrange the labels of the graph so that the new graph looks the same as the old one" isn't exactly arcane, is it?

[maddening]

My humble experience shows me that this might be too much of a digression for many people. Graphs as a visual example of e.g. dependencies or data structures are fine. But if you try to explain something with them you assumes that reader had some prior exposition to graph theory and has some intuitions already. Since I cannot assume they have these intuitions I would have to build them with other examples and the digression could be longer than a paragraphs.

Abstractions are something that works great when you worked enough with some class of specific problems, that your brain notices common parts on its own. If you try to rush it... you get another tutorial when author is enthusiastic and positive and readers feel ashamed and stupid that they "couldn't get it". I'd rather avoid that. If they get foundations, play with them and gain some confidence, they can move on to more challenging and generic definitions.

[soVeryTired]

Aren't Cayley graphs covered in most courses on group theory?