Questions

6-1) Prove that if two graphs G(V,R) and G′(V′,R′) are isomorphic and C = (x1, x2, …, xp) is a cycle in G, then for any isomorphic mapping φ : VV′, φ(C) = (φ(x1), φ(x2), …, φ(xp)) is a cycle in G′.

6-2) Prove that if two graphs G(V,R) and G′(V′,R′) are isomorphic and K = (x1, x2, …, xp) is a clique in G, then for any isomorphic mapping φ : VV′, φ(K) = (φ(x1), φ(x2), …, φ(xp)) is a clique in G′.

6-3) Prove that if two graphs G(V,R) and G′(V′,R′) are isomorphic and XV, then for any isomorphic mapping φ : VV′, the subgraph H of G induced on X is isomorphic to the subgraph H′ induced on φ(x).

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.