It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.

In order to show that one node in the first graph correspond to a particular node (i.e. is isomorphic) in the second graph, its not enough to check that they have the same number of outgoing edges. You have then to check all the connected nodes, and then make sure that those are also isomorphic to the respective same nodes in the same roles at the other graph.

This makes the problem recursive and dependent on the rest of the graph; you can't simply split the graph and solve each sub-problem fast.

    0-1-2     0-2-1

Is that the same as this graph? a'->b' b'->c' c'->a' d'->a'

You can sort the edges alphabetically in the first graph. Then you could take the second graphs labels, and figure out if there is a way to "relabel" it, so when you sort those edges alphabetically, you can the same result.

There are |V|! possible ways to relabel |V| vertices. Other algorithms are better than "try everything", but this shows why it's not trivial. Like a puzzle, you can put the pieces into place, and everything looks right, but then when you get to the end you realize one piece doesn't fit. Does that mean it's not-isomorphic? or maybe you just need to re-arrange the pieces differently? That's why the complexity is so high.

No, there isn’t.

”if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same”

No, it isn’t, unless you know a novel argument that hasn’t been thought of yet by mathematicians.

It is fairly simple for graphs with very few vertices or very few edges, but in general, it isn’t easy at all.