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
- k = t, and i
[1, k], Gi is isomorphic to Hi
- d1 = c1, …,
dk = ck
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.