A Stronger Result of Split

Proposition 3

Let G and H be isomorphic graphs and let (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

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.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.