
EXAMPLE

For n=4, the following 8 edge sets represent the 8 distinct homotopy equivalence classes:
E1={};
E2={{1,2}};
E3={{1,2},{2,3}};
E4={{1,2},{2,3},{1,3}};
E5={{1,2},{2,3},{3,4}};
E6={{1,2},{2,3},{1,3},{3,4}};
E7={{1,2},{2,3},{1,3},{2,4},{3,4}};
E8={{1,2},{2,3},{1,3},{1,4},{2,4},{3,4}};
To demonstrate that this equivalence relation is weaker than both graph isomorphism and graph homeomorphism, consider the following 4 graphs on the 6 vertices {1,2,3,4,5,6}:
G1={{1,2},{1,6},{2,4},{3,4},{3,5},{3,6},{5,6}};
G2={{1,2},{1,3},{2,4},{3,5},{4,5},{4,6},{5,6}};
G3={{1,2},{1,3},{2,4},{3,4},{3,5},{4,6},{5,6}};
G4={{1,2},{1,6},{2,4},{2,6},{3,5},{4,6},{5,6}};
G1 is isomorphic to G2. G3 is homeomorphic to both G1 and G2, but it is not isomorphic to either. G4 is homotopy equivalent to G1, G2, and G3, but not isomorphic nor homeomorphic to any of them.
