1
$\begingroup$

Is there a pair of connected graphs for which the k-wl test always fails (= judges isomorphic when not isomorphic) for any k? If so, please give an example.

How about the following image? Are they non-isomorphic? I'm not sure... enter image description here


now i got they are non-isomorphic. so then, does this correspond to the pair the question asks for?

$\endgroup$
1
  • $\begingroup$ "judges isomorphic when non-isomorphic" makes no sense to me. Can you clarify? $\endgroup$ Jun 29, 2023 at 15:38

1 Answer 1

0
$\begingroup$

Pick any two non-isomorphic $n$-vertex $r$-regular graphs.

Edit to address follow-up question. Yes, the two graphs in your figure are $k$-wl for all $k$, and yes, they are non-isomorphic.

One of the graphs has an induced $C_4$ and the other does not.

$\endgroup$
1
  • $\begingroup$ thanks for your answer. i added an image now $\endgroup$
    – beginner
    Jun 19, 2023 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.