(V1, …, Vk);
(d1 < … < dk)
and
(U1. …, Ut);
(c1 < … < ct)
be the outputs of Split(G) and Split(H), respectively. Let
Gi
(resp. Hj) be the subgraph induced on Vi
(resp. Uj), where i
[1, k]
(resp. j
[1, t]). Then
[1, k], Gi is isomorphic to Hi
Let us apply Split to the two graphs before.
One can easily see that the subgraph of G induced on V
1 is not isomorphic to the subgraph of H induced on
U1. Hence, G and H are not
isomorphic.