Problems 1

(a) Let G1 denote the graph whose vertices are the 3-element subsets of {1, 2, 3, 4, 5, 6, 7}, in which two vertices are adjacent if and only if they are disjoint sets. Let G2 denote the graphs whose vertices are the binary strings of length 7 with exactly four ones, in which two vertices a1a2 . . . a7 and b1b2 . . . b7 are adjacent if ai + bi > 0 for each 1 i 7. Are G1 and G2 isomorphic? Either prove there is an isomorphism, or prove there is not one.

(b) Let H1 denote the graph with vertex set {1, . . . , 16} in which vertices a, b are adjacent if and only if a + b is odd. Let H2 denote the graph whose vertices are the binary strings of length 4, in which two strings are adjacent if either they differ in exactly one position, or they differ in all four positions. Are H1 and H2 isomorphic? Either prove there is an isomorphism, or prove there is not one.