A graph is defined as it always is. A set of edges that connect nodes by their IDs. We can use this arrow notation for convenience. Imagine you have a graph:
a->b
b->c
c->d
d->b
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.
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.