# Given a graph, how to build another "difficult" isomorphic graph from it?

Suppose I want to test an algorithm for graph isomorphism check.

Starting from a given graph, I would do a random permutation of vertices to build the second graph.

Is there a way of making another isomorphic graph that is "more difficult" to check?

• No, because given any labelling of a graph you can make a random labelling of that. So every labelling is equally difficult. That doesn't mean a particular algorithm will take the same time for each labelling. Sep 11 at 14:51
• Maybe it's more interesting to ask for a non-isomorphic graph that is difficult to check? Sep 12 at 1:38
• @Gerry Myerson yes, right. Sep 12 at 6:47