Discussion of Proposition 3

Proposition 3 is useful because it can, for some situations, quickly establish that two graphs are not isomorphic by reducing the problem to smaller graphs. If we discover that the two graphs do not satisfy Proposition 3, we know that they are not isomorphic.

However, for many graphs, such a reduction is of little help, or even no help at all. Regular graphs are a prime example. Furthermore, even if we discover that two given graphs satisfy Proposition 3, we still don't know whether these graphs are isomorphic.

Non-isomorphic graphs satisfying Proposition 3

10-1) Show that these two graphs satisfy Proposition 3 and that they are non isomorphic.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.